{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "今年2月的时候开始学习台大林轩田老师的机器学习课程，感觉很好，这里记录一下作业详解，一来加深自己的理解，而来也可以给需要的小伙伴参考下,话不多说，进入正题。(其实这部分的资料和我之前整理的Learning from data差不多，更全面的部分可以参考Learning from data的习题整理。）\n",
    "\n",
    "我的github地址：  \n",
    "https://github.com/Doraemonzzz\n",
    "\n",
    "个人主页：  \n",
    "http://doraemonzzz.com/\n",
    "\n",
    "作业地址:  \n",
    "https://www.csie.ntu.edu.tw/~htlin/course/ml15fall/\n",
    "\n",
    "参考资料:  \n",
    "https://blog.csdn.net/a1015553840/article/details/51085129  \n",
    "http://www.vynguyen.net/category/study/machine-learning/page/6/  \n",
    "http://book.caltech.edu/bookforum/index.php  \n",
    "http://beader.me/mlnotebook/\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem 1\n",
    "(ii) Detecting potential fraud in credit card charges  \n",
    "(iv) Determining the optimal cycle for traffic lights in a busy intersection  \n",
    "(v) Determining the age at which a particular medical test is recommended\n",
    "\n",
    "质数和自由落体问题可以直接得出结果，所以使用design approach"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem 2\n",
    "这题在Learning from data上也有，当时是选择所有满足的学习种类，这里选择最适合的，应该选择reinforcement learning，因为训练下棋的过程每一步都会给以回馈，下的好给正回馈，下的不好给负回馈，类似训练小狗。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem 3\n",
    "对没有标签的书分类，unsupervised learning。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem 4\n",
    "有脸的图片和没脸的图片都标记出来，supervised learning。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem 5\n",
    "这题我认为是active learning，因为人为设计了实验，更具体的有关active learning，可以参考\n",
    "https://www.cnblogs.com/maybe2030/p/5515042.html"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem 6\n",
    "由题设知$E_{OTS} (g, f)=\\frac 1 L\\sum_{m=1}^L[\\![(N+m)被2整除]\\!]$  \n",
    "我们知道$1$到$N$中被2整除的正整数有$[\\frac N 2]$个，$[]$为高斯函数，意思为向下取整\n",
    "因此\n",
    "$$\n",
    "E_{OTS} (g, f)=\\frac1 L[(1到N+L中被2整除的数的个数)-(1到N中被2整除的数的个数)]\n",
    "=\\frac1 L([\\frac {N+L}2]-[\\frac {N}2])\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem 7\n",
    "这题的意思是在训练集$D$上没有误差，在$\\{x_{N+1} , . . . , x_{N+L}\\}$上的取值就任意了，每个点有两种取值，所以一共有$2^L$种可以拟合的$f$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem 8\n",
    "题目的假设意思应该是每个在训练集无噪声的$f$出现的概率是一样的，所以这些$f$在测试集上每个点出现错误的概率应该是一样的，$E_{OTS}(g,f)=\\frac k L$相当于在$L$个点中挑$k$个，因此\n",
    "$$\n",
    "P(E_{OTS}(g,f)=\\frac k L)=\\frac {C_L^k} {2^L}\n",
    "$$\n",
    "$$\n",
    "\\begin{aligned}\n",
    "E_f[E_{OTS} (g, f)]&=\\sum_{k=0}^L\\frac k L \\frac {C_L^k}{2^L}\n",
    "\\\\&=\\frac {\\sum_{k=0}^LkC_L^k}{L2^L}\n",
    "\\\\&=\\frac {\\sum_{k=1}^L LC_{L-1}^{k-1}}{L2^L}\n",
    "\\\\&=\\frac {2^{L-1}}{2^L}\n",
    "\\\\&=\\frac 1 2\n",
    "\\end{aligned}\n",
    "$$\n",
    "注意这里用到了$kC_n^k=nC_{n-1}^{k-1}$\n",
    "\n",
    "所以\n",
    "$$\n",
    "E_f[E_{OTS} (A_1(D), f)]=E_f[E_{OTS} (A_2(D), f)]\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem 9\n",
    "$P=C_{10}^5(\\frac 1 2)^{10}\\approx0.24609375$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.24609375\n"
     ]
    }
   ],
   "source": [
    "from scipy.special import comb\n",
    "print(comb(10,5)/2**10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem 10\n",
    "$P=C_{10}^9{(\\frac 9{10})^{9}\\frac 1 {10} }\\approx0.387420489 $"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.387420489\n"
     ]
    }
   ],
   "source": [
    "print(comb(10,9)*((0.9)**9)*0.1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem 11\n",
    "$P=C_{10}^1{(\\frac 9{10})^{1}{(\\frac 1 {10})}^{9} }+C_{10}^0{{(\\frac 1 {10})}^{10} }\\approx 9\\times 10^{-9}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "9.1e-09\n"
     ]
    }
   ],
   "source": [
    "print(comb(10,1)*((0.9)**1)*(0.1**9)+comb(10,0)*(0.1**10))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem 12\n",
    "回顾下$Hoeffding$不等式:\n",
    "$$\n",
    "P[| \\mu-v|>\\epsilon]\\le 2e^{-2\\epsilon ^2N}\n",
    "$$\n",
    "因此\n",
    "$$\n",
    "P[v\\le 0.1]=P[0.9-v\\ge 0.8]=P[\\mu-v\\ge 0.8]\\le P[|\\mu-v|\\ge 0.8]\\le 2e^{-2\\times 0.8^2\\times 10}\\approx5.5215451440744015\\times 10^{-6}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem 13\n",
    "这题以及下面一题一定要注意这两句话：They are just used to bind the six faces together. The probability below only refers to drawing from the bag.\n",
    "\n",
    "所以考虑的时候只要看骰子属于哪个包即可。\n",
    "全是orange 1，所以骰子属于B或者C，因此$P=(\\frac 1 2)^5=\\frac 1 {32}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem 14\n",
    "这题要计算某个数字全为orange的概率，取出为全orange 1的情况为从B,C中取出,取出为全orange 2的情况为从A,C中取出，取出为全orange 3的情况为从B,C中取出，取出为全orange 4的情况为从A,D中取出，取出为全orange 5的情况为从B,D中取出，取出为全orange 6的情况为从A,D中取出。所以一共有4中情形(A,C),(B,C),(A,D),(B,D),注意全A,B,C,D的情形都被算了两次，所以一共有$4\\times2^5-4=92$种情形，概率为$P=\\frac {92}{4^5}=\\frac {31}{256}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem 15\n",
    "这题是使用最标准的PLA，下面编程实现下"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(45, 135, array([-3.       ,  3.0841436, -1.583081 ,  2.391305 ,  4.5287635]))"
      ]
     },
     "execution_count": 88,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "file=open('data.txt')\n",
    "data=[]\n",
    "\n",
    "#增加w0\n",
    "for i in file.readlines():\n",
    "    #增加w0\n",
    "    temp1='1 '+i.replace('\\t',' ').replace('\\n','')\n",
    "    #分隔数据\n",
    "    temp2=temp1.split(' ')\n",
    "    #转化为float\n",
    "    temp3=np.array(list(map(float,temp2)))\n",
    "    #转化为np.array存入数据\n",
    "    data.append(temp3)\n",
    "\n",
    "#维度\n",
    "n=len(data[0])-1\n",
    "#数据组数\n",
    "m=len(data)\n",
    "\n",
    "#定义sign函数\n",
    "def sign(x):\n",
    "    if x>0:\n",
    "        return 1\n",
    "    else:\n",
    "        return -1\n",
    "\n",
    "#定义判别函数，判断所有数据是否分类完成,n为数据维度\n",
    "def Judge(x,w,n):\n",
    "    flag=1\n",
    "    for i in x:\n",
    "        if sign(i[:n].dot(w))*i[-1]<0:\n",
    "            flag=0\n",
    "            break\n",
    "    return flag\n",
    "\n",
    "#定义PLA,n为数据维度,m为数据数量,k为步长\n",
    "def PLA(x,k,n,m):\n",
    "    #初始化向量\n",
    "    w=np.zeros(n)\n",
    "    #记录最后一个更新的向量\n",
    "    last=0\n",
    "    #记录次数\n",
    "    t=0\n",
    "    if Judge(x,w,n):\n",
    "        pass\n",
    "    else:\n",
    "        #记录取哪个元素\n",
    "        j=0\n",
    "        while Judge(x,w,n)==0:\n",
    "            i=x[j]\n",
    "            #print(i[:n],i[-1])\n",
    "            if sign(i[:n].dot(w))*i[-1]<0:\n",
    "                w+=k*i[-1]*i[:n]\n",
    "                t+=1\n",
    "                last=j\n",
    "            j+=1\n",
    "            if(j>=m):\n",
    "                j=j%m\n",
    "    return t,last,w\n",
    "PLA(data,1,n,m)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "所以这题答案为更新了45次，最后一个更新的元素索引为136(python中从0开始数)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem 15"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "打乱之后运行2000次，作出直方图"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 92,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import random\n",
    "import matplotlib.pyplot as plt\n",
    "plt.rcParams['font.sans-serif']=['SimHei'] #用来正常显示中文标签\n",
    "plt.rcParams['axes.unicode_minus']=False #用来正常显示负号\n",
    "\n",
    "x=[]\n",
    "for i in range(2000):\n",
    "    random.shuffle(data)\n",
    "    x.append(PLA(data,1,n,m)[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYAAAAETCAYAAAA/NdFSAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAAHTJJREFUeJzt3XuYXWV99vHvnQMQkgChGYLxQEBT\nqzWJ4hgSDbyDEjQclEYtqQekQCMWsK21Jcj08gWDVV6kr1VBolGpChatREEpASUQMQFmwADl4DEg\n0choQkIUEPDXP54nzmbYk1l7MjN7w3N/rmtdrL32b6/1rD1k3Xs966SIwMzMyjOq2Q0wM7PmcACY\nmRXKAWBmVigHgJlZoRwAZmaFcgBY00maKEnNbodZaRwAttMkjZY0egfvj5E0qub1f0o6tqbkw8Dp\n/Xx2X0ltDbbnBEkn97PsUZJ2qXmtPp/tkPRvO5j3qZJ2k/RdSTMk/ZOkPSRdJOmQCm1bIKm9kfUx\nGy4OABsKRwDdkrry8ICkX+TxbuA2YEZN/aPA72teHwpc2s+8ZwNXSNpd0uGS7pZ0m6RuST+Q9CNJ\nk7YXS3oecCawMk9aDGxvVxfQDSzLtQKulzSzZnlvBu7ZwbqOATqBJ4DxwKKI2Aq8Fnig3gck/auk\n1+aXbwNe2d/MJb1K0jckXS1pQZ62Sw6YByTdIengHbQPSXtKuiz/DdZK+vM8/ZOSNtYMj0g6Lr93\nUa7/iaQj87RRkrbU1K/Z0XLtGSgiPHjY6QF4EzAmjy8Blubx3YEzgNE1tV8AjsnjLwb+AGzsM+xR\nU38GcFCFNkwghc2bG2j3McCPgD2AccAm4C7gBzXDx3PtbsBfAn8H3JLX89+AQ4Bf1sxz1z7LOAj4\nFfAa4GvAgn7asifwQ1IgdgAPApOAU4EvkcKnHfglMHEH63Qeaa9K+e9yb52ascDdwL7AkcB/5Okz\ngZ68rD8Drm72/1sehm8YUzkpzHbsbcB80saq1unArIh4UtIrgMuAfYD5kt4O3AecEREf3f4BSb+m\nZg8hIv5V0vMknUb65V17+foo4JGI+DzwXOCLwO2SbgEOi4gtO2p0RKyQ9Hrgr4CJwPKI+KeatnwK\nuDe/3IW0sZ9N2hDfTQqM9wCj8h7GC4CHJb08Ih6WNBboAravaxsp4Op5DtAZEdflZf8ceB5wLLAk\nIp4g7c38mhScXf3M51hgTkQE8A1JX5I0OSJ+XVPzTuC/I2KjpJcCa/L3cXvuFRsPvIIUgPYs5QCw\noXIicJeka7ZPkDQnT9/e5bEOeAnwWeAbpO6YG4HTJH0wIs7KdWOAxyTtC6wmdRktB34DPAl8itQN\ns4kUAI8BRMS9kn5I6v75MrC/pG8DD5NCY1dSgIwFvhIRS/LyTgP2Im0EZ+dukf8TEScCRwPn5LpH\ngJ+SguZR4CFgM/Bq4JMR8SFJXwE+FhEP58+8j7SxfSK/ngl8vubQw1hgckRMiYh7gHvy8ZRj8nt3\n5brJ+TudCOwH1G7M65kMbJA0Lc/n4T7vvxf4izx+J3BGbvt84GcRsSUH9rGS3pWX9zcR4W6gZ5Nm\n74J4ePYMpA3h3uQuINKGv6NO3RdIG7jdgFeRflnfCMzI72/uU78EOD6PvxC4KY8vBvbsU9tJ2tjv\nVWe5XwKOqjN9Cqm7Y8/8+mRgWR7fq6Zuf+A4YDrpmMUk4K9J3U4rcs33gb37+X5mAHf0mfZyoLvP\ntPeRwuaUmvb8nLQ3tRa4eYC/w0eA/8n1dwGX9Xl/LnBVzetdgTtIAXg/cHSe/o/A4Xn8LcCdzf5/\nzMPQDt4DsJ2SD25+EvhdzeR9Sb/M35BrRpH6598TEd/ZXhQRj5L60pH0RmCppPNIv/L783fA2Xl8\nHPBx4Pg8jzcBC4EfN7gaHwAei4h/zq9fCszJbXyopm5v4B+As/L6XQE8Tgq+Vflg9MSI2NTPco4H\nvirpfOCGiFhB6uK5v7YoIs6XdBlwk6SrI+LTkrYfQziQ1F010PrcTTr28BJSaNV6J0896P4B4JJI\nXW3jgBsl3RoRH6tp09ckXSBpn4h4cIDl2zOEA8B2SkR8l7TB/CNJS4AJEdG5g4++XNKfRMRySXOB\nTwCXkDaGj9f7QD47ZRHwgKTXkbpi3irp8xFxPfAd4Cbg2qrtl7QfcBTplziSdgcOB34oqSMiVtWs\na7ekeaS9lYOA1wNHRMQjkr4OrAC+289yZgFvBV5G2oP4Ug7Pu/I6I+lFwO4RcXtEPJCPY7wY+HFE\nXC7pCeB1wNd3tE4R8QfgYkl7AN+IiD8eK8hhfDRpT2m7OcAF+bOPSPoJMFPSERHxmfy53UgB+Icd\nLdueWXwaqI0YSXMlfQM4jNSd8jNJbyMduH13RJxP+lHySJ2P70bqh/4P0kHUy4H3k85ymQYQEdsi\nor8DrPXaM4p0POKDkQ7YjiKdIvpZUh/5ckkH9vnYVNLB1/8GLiIdx4C0UT6EtFfQdznTgK8Cp0bE\n1ojoJv2S///A80ndO9vn/Z+S9pL0HFL32G01szoD+EBEDHgPd6VrHf6ep27oIQXdr/rspfwM+GtJ\nL5V0NOnvcw+p///tkiYAHyR1vQ107MGeSZrdB+Xh2TeQuhQ+XGf6C4B3UHOaJOk00b3y+AuBNwJd\n+fUo0ob4ftJG8mSgrc58dwd2q3l9FzCp5vUoUnfRFcCRNdPfQPo1L9Iv8+8Cn655/1BS6LwXGJun\nibSB/D5wAmkjvhC4ldRn/lPg4Jp5HJnbf1KfNj8nfx/fBxbWTD+DdJrnj4G31kw/AljVZx7PB27v\n52/wt8AX6kz/B9IB69ppU0kHzrcBvwBOztNfTAqgLcCVwAua/f+Wh6Edmt4AD8++gdRHft4gPndz\n3uD8ZX59AHA96SDtZOD/kU5L3JA3VD2kYw+/J51Js30+Pwam1LwW6QDnTX03YqTTHSeQDpq+u06b\nXgJ8D5iVg+Y60rn/++b330HqcvrT/LoDuCbPd3x+72nn/ZP64Dfm/45r9t/MQ5mDIvxEMDNJCv9j\nsMI4AMzMCuWDwGZmhXIAmJkVqqWvA5g8eXJMmzat2c0wM3tG6e7u/nVEDHgb9ZYOgGnTptHV1d/9\nrszMrB5J91WpcxeQmVmhHABmZoVyAJiZFcoBYGZWKAeAmVmhHABmZoVyAJiZFapSAEhaLmmNpH4f\n8NFfjaQpkm4bqM7MzEbWgBeCSVoIjI6IuZI+J2l6RPyogZrzSPdirzQvs0ZMW/Ktpi17/UeObNqy\nzYZClT2ADuCyPL4SmFe1Jj/y7rek+55XmpekxZK6JHX19PRUaJ6ZmQ1GlQAYT3oAB8Am0sM5BqzJ\nj6T7F2BJI/OKiGUR0R4R7W1tA97KwszMBqlKAGwjd+GQnpxU7zP1apYAF0TEQw3Oy8zMRkCVDXA3\nvV01s4D1FWsOA06RtAp4uaTPVpyXmZmNgCp3A10BrJY0FVgALJK0NCI6d1AzJyIu2f6mpFURcZKk\nPfrWDdmamJlZQwbcA4iIraSDt2uBQyNiXZ+Nf72aLX3e76hSZ2ZmI6fS8wAiYjO9Z+8MuqaROjMz\nG14+CGtmVigHgJlZoRwAZmaFcgCYmRXKAWBmVigHgJlZoRwAZmaFcgCYmRXKAWBmVigHgJlZoRwA\nZmaFcgCYmRXKAWBmVigHgJlZoRwAZmaFcgCYmRVqWANA0t6S5kuaPJzLMTOzxlUKAEnLJa2R1Fm1\nRtIk4EpgNnCdpDZJYyTdL2lVHmYMyVqYmVnDBnwkpKSFwOiImCvpc5KmR8SPBqoBpgLvi4i1OQwO\nBHqASyPi9GFYFzMza0CVPYAOep/huxKYV6UmIq7PG/9DSHsBa4A5wFGSbs57DE8LIEmLJXVJ6urp\n6WlsbczMrLIqATAe2JDHNwFTqtZIEnAssBl4HLgFOCwiZgNjgSP6zigilkVEe0S0t7W1NbAqZmbW\niAG7gIBtwLg8PoH6oVG3JiICOEXSh4A3Aisi4rFc1wVMH2S7rcVMW/KtZjfBzBpUZQ+gm95un1nA\n+io1kk6XdFyethfwEPBFSbMkjQaOAdYNtuFmZrZzquwBrABWS5oKLAAWSVoaEZ07qJlDCpfLJJ0E\n3Ek6NrABuAQQ8M2IuHboVsXMzBoxYABExFZJHcB84NyI2EifX+51arbkt+b3md2dwMydbbSZme28\nKnsARMRmes/yGXSNmZm1Dt8KwsysUA4AM7NCOQDMzArlADAzK5QDwMysUA4AM7NCOQDMzArlADAz\nK5QDwMysUA4AM7NCOQDMzArlADAzK5QDwMysUA4AM7NCOQDMzArlADAzK9SwBoCkvSXNlzR5OJdj\nZmaNqxQAkpZLWiOps2qNpEnAlcBs4DpJbVXnZWZmw2/AAJC0EBgdEXOBAyRNr1gzE3hfRJwDXA0c\nWGVeZmY2MqrsAXTQ+6zflcC8KjURcX1ErJV0CGkvYE2VeUlaLKlLUldPT0/F1TAzs0ZVCYDxwIY8\nvgmYUrVGkoBjgc3A41XmFRHLIqI9Itrb2toqroaZmTWqSgBsA8bl8Qn9fKZuTSSnALcDb6w4LzMz\nGwFVNsDd9HbVzALWV6mRdLqk4/K0vYCHKs7LzMxGwJgKNSuA1ZKmAguARZKWRkTnDmrmkMLlMkkn\nAXeS+vwn1qkzM7MmGDAAImKrpA5gPnBuRGwE1g1QsyW/Nb/P7PqrMzOzEVZlD4CI2Ezv2TuDrmmk\nzszMhpcPwpqZFcoBYGZWKAeAmVmhHABmZoVyAJiZFcoBYGZWKAeAmVmhHABmZoVyAJiZFcoBYGZW\nKAeAmVmhHABmZoVyAJiZFcoBYGZWKAeAmVmhHABmZoWqFACSlktaI6mzao2kPSVdJWmlpMsl7SJp\njKT7Ja3Kw4yhWhEzM2vMgAEgaSEwOiLmAgdIml6x5u3A+RFxOLAReAMwE7g0IjrycMdQroyZmVVX\nZQ+gg95HOK4E5lWpiYgLIuKaPK0NeJD0EPijJN2c9xgqPZLSzMyGXpUAGA9syOObgCmN1EiaC0yK\niLXALcBhETEbGAsc0XdGkhZL6pLU1dPTU3lFzMysMVUCYBswLo9P6OczdWsk7Q18Ajghv3d7RPwy\nj3cBT+tOiohlEdEeEe1tbW2VVsLMzBpXJQC66e32mQWsr1IjaRfgq8AZEXFffu+LkmZJGg0cA6wb\nbMPNzGznVOmDXwGsljQVWAAskrQ0Ijp3UDMHOBE4EDhT0pnAhcDZwCWAgG9GxLVDtypmZtaIAQMg\nIrZK6gDmA+dGxEb6/HKvU7OFtMG/sM4sZ+5so83MbOdVOgsnIjbTe5bPoGvMzKx1+EpgM7NCOQDM\nzArlADAzK5QDwMysUA4AM7NCOQDMzArlADAzK5QDwMysUA4AM7NCOQDMzArlADAzK5QDwMysUA4A\nM7NCOQDMzArlADAzK5QDwMysUA4AM7NCVQoAScslrZHUWbVG0p6SrpK0UtLl+SHxleZlZmbDb8AA\nkLQQGB0Rc4EDJE2vWPN24PyIOBzYCLyhyrzMzGxkVNkD6KD3Wb8rgXlVaiLigoi4Jk9rAx6sMi9J\niyV1Serq6emp0DwzMxuMKgEwHtiQxzcBUxqpkTQXmBQRa6vMKyKWRUR7RLS3tbVVWgkzM2vcmAo1\n24BxeXwC9UOjbo2kvYFPAG9uYF5mZjYCqmyAu+ntqpkFrK9Skw/6fhU4IyLua2BeZmY2AqrsAawA\nVkuaCiwAFklaGhGdO6iZA5wIHAicKelM4MJ+6szMrAkGDICI2CqpA5gPnBsRG4F1A9RsIW3wL+w7\nvzp1ZmbWBFX2AIiIzfSevTPomkbqzMxsePkgrJlZoRwAZmaFcgCYmRXKAWBmVigHgJlZoRwAZmaF\nqnQaqJm1jmlLvtW0Za//yJFNW7YNPe8BmJkVygFgZlYoB4CZWaEcAGZmhXIAmJkVygFgZlYoB4CZ\nWaEcAGZmhXIAmJkVygFgZlaoSgEgabmkNZI6G6mRNEXS6prXz5X0gKRVeWjbueabmdlgDRgAkhYC\noyNiLnCApOlVaiRNAi4GxteUHgScExEdeegZmtUwM7NGVdkD6KD3Gb4rgXkVa54EjgW21tTNAU6S\ndKukD9dbmKTFkrokdfX0OB/MzIZLlQAYD2zI45uAKVVqImJrRGzpU3cVKSxeBcyVNLPvjCJiWUS0\nR0R7W5t7iMzMhkuVANgGjMvjE/r5TJUagO9HxMMR8SRwG/C07iQzMxsZVQKgm95un1nA+kHWAFwt\n6TmSdgcOB+6s3FIzMxtSVR4IswJYLWkqsABYJGlpRHTuoGZOP/M6C7gO+D3w6Yi4d/BNNzOznTFg\nAETEVkkdwHzg3IjYCKwboGZLzXsdNePXAX82JC03M7OdUumRkBGxmd6zfAZdY2ZmrcNXApuZFcoB\nYGZWKAeAmVmhHABmZoVyAJiZFcoBYGZWKAeAmVmhHABmZoVyAJiZFcoBYGZWKAeAmVmhHABmZoVy\nAJiZFcoBYGZWKAeAmVmhKj0PwJ4Zpi35VrObYGbPIA6AYeANsZk9E1TqApK0XNIaSZ2N1EiaIml1\nzeuxkq6QdKOkE3au6WZmtjMGDABJC4HRETEXOEDS9Co1kiYBFwPja0pPA7oj4jXAWyRNHJK1MDOz\nhlXZA+ig91m/K4F5FWueBI4FtvZTdwPQ3ndGkhZL6pLU1dPTU6F5ZmY2GFUCYDywIY9vAqZUqYmI\nrRGxpdF5RcSyiGiPiPa2trYKzTMzs8GoEgDbgHF5fEI/n6lS00idmZkNsypnAXWTunTWArOAewdZ\nU1v3tVy3tsH2mrUMn+1lz3RVAmAFsFrSVGABsEjS0ojo3EHNnH7mdTHwbUkHAy8Fbhp8083MbGcM\n2AUTEVtJB2/XAodGxLo+G/96NVtq3uuoGb8PmA/cCBwWEU/u/CqYmdlgVLoQLCI203v2zqBrct0v\nqtSZmdnw8kFYM7NCOQDMzArlADAzK5QDwMysUA4AM7NCOQDMzArlADAzK5QDwMysUA4AM7NCOQDM\nzArlADAzK5QDwMysUA4AM7NCOQDMzArlADAzK5QDwMysUJUCQNJySWskdTZS03eapDGS7pe0Kg8z\ndn4VzMxsMAYMAEkLgdERMRc4QNL0KjX9fG4mcGlEdOThjqFdHTMzq6rKHkAHvY9wXAnMq1hTb9oc\n4ChJN+e9g6c9klLSYkldkrp6enoqroaZmTWqSgCMBzbk8U3AlIo19abdQnoY/GxgLHBE3xlFxLKI\naI+I9ra2tqrrYWZmDaryUPhtwLg8PoH6oVGvpt602yPisTytC3had5KZmY2MKnsA3fR2+8wC1les\nqTfti5JmSRoNHAOsG0yjzcxs51XZA1gBrJY0FVgALJK0NCI6d1AzB4g6024HLgEEfDMirh26VTEz\ns0YMGAARsVVSBzAfODciNtLnl3udmi0AdaZtIZ0JZGZmTVZlD4CI2EzvGT2Va6p8zszMmsNXApuZ\nFarSHoCZGcC0Jd9qynLXf+TIpiz32c57AGZmhXIAmJkVygFgZlYoB4CZWaEcAGZmhXIAmJkVygFg\nZlYoB4CZWaEcAGZmhXIAmJkVygFgZlYoB4CZWaEcAGZmhXIAmJkV6ll9O+hm3brWzIaWb0M9PCrt\nAUhaLmmNpM5GaqpOMzOzkTfgHoCkhcDoiJgr6XOSpkfEjwaqAWZUmdZ3XmZmraKZvQgjsfdRpQuo\ng97n+q4E5gF9N9r1al5RcVrfMFkMLM4vt0m6t0Ibh8Jk4NcjtKxGuW2D47YNjts2OEPaNn10pz6+\nX5WiKgEwHtiQxzcBB1asqTrtKSJiGbCsQruGlKSuiGgf6eVW4bYNjts2OG7b4LRy2/pT5RjANmBc\nHp/Qz2fq1VSdZmZmTVBlA9xN6qoBmAWsr1hTdZqZmTVBlS6gFcBqSVOBBcAiSUsjonMHNXOAqDit\nVYx4t1MD3LbBcdsGx20bnFZuW12KiIGLpEnAfOCGiNhYtabqNDMzG3mVAsDMzJ59fBDWGiZpb0nz\nJU1udlvMbPCKDgBJUyStzuNjJV0h6UZJJzS5XXtKukrSSkmXS9qlVa6gzl14VwKzgesktbVK2+CP\nf9Pb8nhLtEvSGEn3S1qVhxmSzpJ0i6RPNbNttSRdIOnoPN4q3917ar63H0i6qIXaNknStyV1Sboo\nT2uJtlVVbADkDdnFpGsTAE4DuiPiNcBbJE1sWuPg7cD5EXE4sBFYRL6CGjggX1XdLDOB90XEOcDV\nwGtbqG0A5wHjaq9Ob4F2zQQujYiOiOgAdiGdDTcbeFDSYU1sGwCSDgb2jYgrWum7i4gLa7631cBP\nWqVtwDuBL+dz/ydK+ucWalslxQYA8CRwLLA1v+6g9yrlG4CmXdARERdExDX5ZRvwDp5+BXVTRMT1\nEbFW0iGkDdjrW6Vtkl4L/JYUmh20SLtIZ7sdJelmScuB1wH/FekA3NXAwU1sG5LGAp8B1kt6E631\n3QEg6bnAFOB5tE7bfgO8TNJewPOB/WmdtlVSbABExNaI2FIzqe9VylNGvlVPJWkuMAn4OS3UNkki\nhedm0qm9TW+bpF2AfwGW5Emt9Pe8BTgsImYDY0kXQ7ZK2wCOA+4CziWF+im0VvsgtelCWuvv+j3S\nLRfeC9xN2rNrlbZVUmwA1NFSVylL2hv4BHACLda2SE4BbgdeTWu0bQlwQUQ8lF+30nd2e0T8Mo93\n0Vptg3SPrmX5tOwvkfaAW6Z9kkYBhwKraK3v7oPAyRFxNnAP8DZap22VtHwDR1DLXKWcf81+FTgj\nIu6jtdp2uqTj8su9gI/QGm07DDhF0irg5cDRtEa7AL4oaZak0cAxpF+xrdI2gB8DB+TxdmAardW+\ng4GbcpdZy/xbIO2dz8h/14NonX8L1UVE0QOwKv93P+B/gI+TdtlHN7FN7yF1r6zKw7uAdcD5pF3N\nPZvYtknANaRfiRcAe7ZK22r/psAerdIu4GWkvaU7gHNIP7xuzP+v3Qvs3+TvayLpB8cNwJr8b6El\nvrvcvg8DC/N4K/1dZ+dtxrb8b6Jl2lZ18IVgNfItKuYBV8dTjw80XStfQd2qbWvVdgFIGgccCdwa\nET9tdnv6avHvzm0bIg4AM7NC+RiAmVmhHABmZoVyAFjRlNWb3uB89pX0mqFrmdnwcwBYUSR9NN/3\nabSkfyedvvfvdUrPkXSEpPGSVkiaKOnwmvlMkPR/a+qPA17ZzzLPlnSopHMkLcnzujqfPmjWNFUe\nCGP2bDIGeAvwIPBW0oVsbZJmADdGxJm57rXA0oj4naRpwOPAuZLujoifR8Q2Sc+XdFJEfJZ0EdCj\n+T46AJsj4i8kTSDdbmQusA+wL+k0y99GxJP5Iici4g8jsO5mT+EAsNJ8ICIek7QEeBW9Fz19lHQp\nP5LmA7+IiN/lzzwREY9KOgJ4IenWHJBuAXCRpPtJNyr7IPA74EX03pJiT+BPgFOBHwDfz+MvknRD\nrj0GuHnY1tisHw4AK4akE4GTJH0MOAo4HNgb2JV0JfGukk4lXaz1U0kHkULi+ZK+Rtq4ryNt7ImI\n3wLvkPRR4CxgMelGdL8BvpwX+yQpZD4GvJi0BzATOJN0Be67I8Ibf2sKB4AVIyKWS3oMmBAR8wAk\nXQxsjYjT8uu/Ba4ibayfS7pS9xbg9Ij4Sd95SvoscGreQ9iH1PVzRU3JGFI4vJN0hejjpCtbXwn8\nHmi5i8CsHD4IbMXKv/D3AXokfThP/gzpJnxExNcj3Zb7StJtr/t+/nW57tF81tCrSVeB1tqPdBfL\nd5G6iK4E3kQKgLnATUO8WmaVOQCsSLmffzmpC+ZsUp/8+yPi8Trl/wUcL2nU9tNDJY0ndRWdkWuW\nAJcA35N01vYPRsSNpHvEf4d0p80v52XcSur7v2VYVtCsAncBWTHyGTdHk7p2rgXeHBH357dPIj2o\nBUB5ACAieiRdQbp5268k3ZvfuhQYU6cb6ZOSLgf+Md/n59OkB9V0AvdJ2h/4c+Ax4EDSLaLNRpwD\nwEryN8DPSN08pwBHS3qc9JCW3YC9JI0h3RFz19oPRsSH8nn/xwOHRMQvACQdBVwVEV+pqT1V0l+R\nHhM4idQF9FPSk8FeCnweeD/wK+Brkt5W7/iC2XDzzeCsGJJGNeN8e0ljIuKJPC5gVEQ8uf11+B+h\nNYkDwMysUD4IbGZWKAeAmVmhHABmZoVyAJiZFcoBYGZWqP8Ft7Ag3m12O+0AAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x1ff7ea39358>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.hist(x,normed=True)\n",
    "plt.xlabel(\"迭代次数\")\n",
    "plt.title(\"平均运行次数为\"+str(sum(x)/2000))\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem 16\n",
    "这里修改系数$\\eta=0.5$,打乱之后运行2000次，作出直方图"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "x1=[]\n",
    "for i in range(2000):\n",
    "    random.shuffle(data)\n",
    "    x1.append(PLA(data,0.5,n,m)[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYAAAAETCAYAAAA/NdFSAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAAHTBJREFUeJzt3XuYXWV99vHvnQMQkghJGYPxwEFT\nkZpEcQyJBt4BCRoOSqOWFBUt0qgFbGttCZJevtBAgRfpa1WQSFQKggUqQUBKUAlECIcZMYGCeAxI\nNDKamBAFBPz1j+eJsxn2ZNaezMze8Nyf61pX1l77t9d61t6Zde/1rMNWRGBmZuUZ0ewGmJlZczgA\nzMwK5QAwMyuUA8DMrFAOADOzQjkArOkkjZekZrfDrDQOANtukkZKGrmN50dJGlHz+D8lHV1TciZw\nch+v3V1SW4PtOU7Sh/tY9ghJO9Q8Vq/Xdkj6t23M+0RJO0n6tqSpkv5R0oskXSjpwAptmyupvZH1\nMRsqDgAbDIcBXZI68/CIpJ/n8S7gHmBqTf0TwO9rHh8EXN7HvGcA10raWdKhkh6QdI+kLknfk/RD\nSRO2Fkt6GXAqsDxPWgBsbVcn0AUsybUCbpE0rWZ57wS+v411HQUsAp4GxgLzI2IzcDDwSL0XSPpX\nSQfnh8cAb+hr5pLeKOkaSTdKmpun7ZAD5hFJ90o6YBvtQ9Iukq7In8Edkv4sT/+spPU1w+OSjs3P\nXZjrfyzp8DxthKRNNfWrtrVcex6KCA8etnsA3gGMyuMLgcV5fGfgFGBkTe2XgaPy+KuBPwDrew0v\nqqk/Bdi/QhvGkcLmnQ20+yjgh8CLgDHABuB+4Hs1w6dz7U7AXwB/C9yd1/PfgAOBX9TMc8dey9gf\n+CXwZuAqYG4fbdkF+AEpEDuAR4EJwInApaTwaQd+AYzfxjqdS9qrUv5cHqxTMxp4ANgdOBz4jzx9\nGtCdl7UPcGOz/295GLphVOWkMNu2Y4A5pI1VrZOB6RHxjKTXA1cALwbmSHoP8BBwSkScvfUFkn5F\nzR5CRPyrpJdJOon0zbv28vURwOMR8SXgpcAlwBpJdwOHRMSmbTU6IpZJeivwl8B4YGlE/GNNWz4H\nPJgf7kDa2M8gbYgfIAXGR4AReQ/jFcBjkl4XEY9JGg10AlvXtY0UcPW8BFgUETfnZf8MeBlwNLAw\nIp4m7c38ihScnX3M52hgZkQEcI2kSyXtFhG/qql5H/DfEbFe0r7Aqvx+rMm9YmOB15MC0F6gHAA2\nWD4I3C/ppq0TJM3M07d2eawGXgNcBFxD6o65DThJ0icj4rRcNwp4UtLuwEpSl9FS4NfAM8DnSN0w\nG0gB8CRARDwo6Qek7p+vAHtJ+gbwGCk0diQFyGjgqxGxMC/vJGBX0kZwRu4W+T8R8UHgSOCMXPc4\n8BNS0DwB/AbYCLwJ+GxE/IukrwKfiojH8ms+RtrYPp0fTwO+VHPoYTSwW0RMiojvA9/Px1OOys/d\nn+t2y+/peGAPoHZjXs9uwDpJe+b5PNbr+Y8Cf57H7wNOyW2fA/w0IjblwD5a0vvz8v46ItwN9ELS\n7F0QDy+cgbQhnEjuAiJt+Dvq1H2ZtIHbCXgj6Zv1bcDU/PzGXvULgQ/k8VcCd+bxBcAuvWoXkTb2\nu9ZZ7qXAEXWmTyJ1d+ySH38YWJLHd62p2ws4FphCOmYxAfgrUrfTslxzOzCxj/dnKnBvr2mvA7p6\nTfsYKWxOqGnPz0h7U3cAd/XzOZwF/E+uvx+4otfzs4Abah7vCNxLCsCHgSPz9H8ADs3j7wLua/b/\nMQ+DO3gPwLZLPrj5WeB3NZN3J30zf1uuGUHqn/9IRHxra1FEPEHqS0fS24HFks4lfcvvy98Cp+fx\nMcCngQ/kebwDmAf8qMHV+ATwZET8U368LzAzt/E3NXUTgb8HTsvrdy3wFCn4VuSD0eMjYkMfy/kA\ncKWk84BbI2IZqYvn4dqiiDhP0hXAnZJujIjPS9p6DGE/UndVf+vzAOnYw2tIoVXrfTz7oPsngMsi\ndbWNAW6T9N2I+FRNm66SdL6kF0fEo/0s354nHAC2XSLi26QN5h9JWgiMi4hF23jp6yT9SUQslTQL\n+AxwGWlj+FS9F+SzU+YDj0h6C6kr5t2SvhQRtwDfAu4Evlm1/ZL2AI4gfRNH0s7AocAPJHVExIqa\nde2SNJu0t7I/8FbgsIh4XNLXgGXAt/tYznTg3cBrSXsQl+bwvD+vM5JeBewcEWsi4pF8HOPVwI8i\n4mpJTwNvAb62rXWKiD8AF0t6EXBNRPzxWEEO4yNJe0pbzQTOz699XNKPgWmSDouIL+TX7UQKwD9s\na9n2/OLTQG3YSJol6RrgEFJ3yk8lHUM6cPuhiDiP9KXk8Tov34nUD/0fpIOoVwMfJ53lsidARGyJ\niL4OsNZrzwjS8YhPRjpgO4J0iuhFpD7ypZL26/WyyaSDr/8NXEg6jgFpo3wgaa+g93L2BK4EToyI\nzRHRRfom//+Bl5O6d7bO+z8l7SrpJaTusXtqZnUK8ImI6Pce7krXOvwdz97QQwq6X/baS/kp8FeS\n9pV0JOnz+T6p//89ksYBnyR1vfV37MGeT5rdB+XhhTeQuhTOrDP9FcB7qTlNknSa6K55/JXA24HO\n/HgEaUP8MGkj+WGgrc58dwZ2qnl8PzCh5vEIUnfRtcDhNdPfRvo2L9I3828Dn695/iBS6HwUGJ2n\nibSBvB04jrQRnwd8l9Rn/hPggJp5HJ7bf3yvNr8kvx+3A/Nqpp9COs3zR8C7a6YfBqzoNY+XA2v6\n+Az+Bvhynel/TzpgXTttMunA+Rbg58CH8/RXkwJoE3Ad8Ipm/9/yMLhD0xvg4YU3kPrIzx3A6+7K\nG5y/yI/3Bm4hHaTdDfh/pNMS1+UNVTfp2MPvSWfSbJ3Pj4BJNY9FOsB5Z++NGOl0x3Gkg6YfqtOm\n1wDfAabnoLmZdO7/7vn595K6nP40P+4AbsrzHZufe855/6Q++PX53zHN/sw8lDkowr8IZiZJ4T8G\nK4wDwMysUJUOAktaKmmVpD7P6uirRtIkSff0V2dmZsOr3wCQNI90H5dZwN6SpjRYcy7pAFyleZmZ\n2fCoch1AB+n+LZDOFJhNunlWvzX5POff0nPvk37nJWkB6QpPxo4d+4Z99tmn0oqYmVnS1dX1q4jo\n9zbqVQJgLOmsC0j3Xul9XnTdmnwe8j+T7jeyrOq8ImIJ+Xa97e3t0dnZ1/2uzMysHkkPVamrcgxg\nC7kLh3S6XL3X1KtZCJwfz76Uvsq8zMxsGFTZAHeRumognQu9tmLNIcAJklaQLvu/qOK8zMxsGFTp\nAloGrJQ0GZgLzJe0OJ59n5feNTMj4rKtT0paERHH53uTPKtu0NbEzMwa0u8eQKSfu+sg3Yb2oIhY\n3WvjX69mU6/nO6rUmZnZ8Kl0N9CI2EjP2TsDrmmkzszMhpYPwpqZFcoBYGZWKAeAmVmh/Itg9ry2\n58Lrm7bstWcd3rRlmw0G7wGYmRXKAWBmVigHgJlZoRwAZmaFcgCYmRXKAWBmVigHgJlZoRwAZmaF\n8oVgNiiaeUGWmQ2M9wDMzArlADAzK5QDwMysUA4AM7NCDWkASJooaY6k3YZyOWZm1rhKASBpqaRV\nkhZVrZE0AbgOmAHcLKlN0ihJD0takYepg7IWZmbWsH5PA5U0DxgZEbMkfVHSlIj4YX81wGTgYxFx\nRw6D/YBu4PKIOHkI1sXMzBpQZQ+gg54fcV8OzK5SExG35I3/gaS9gFXATOAISXflPYbnBJCkBZI6\nJXV2d3c3tjZmZlZZlQAYC6zL4xuASVVrJAk4GtgIPAXcDRwSETOA0cBhvWcUEUsioj0i2tva2hpY\nFTMza0SVANgCjMnj4/p4Td2aSE4A1gBvB9ZExC9yXScwZYDtNjOz7VQlALro6faZDqytUiPpZEnH\n5mm7Ar8BLpE0XdJI4Chg9UAbbmZm26fKvYCWASslTQbmAvMlLY6IRduomUkKlyskHQ/cRzo2sA64\nDBDw9Yj45uCtipmZNaLfAIiIzZI6gDnAORGxnl7f3OvUbMpPzek1u/uAadvbaDMz236V7gYaERvp\nOctnwDVmZtY6fCsIM7NCOQDMzArlADAzK5QDwMysUA4AM7NCOQDMzArlADAzK5QDwMysUA4AM7NC\nOQDMzArlADAzK5QDwMysUA4AM7NCOQDMzArlADAzK5QDwMysUA4AM7NCDWkASJooaY6k3YZyOWZm\n1rhKASBpqaRVkhZVrZE0AbgOmAHcLKmt6rzMzGzo9RsAkuYBIyNiFrC3pCkVa6YBH4uIM4Abgf2q\nzMvMzIZHlT2ADnp+7H05MLtKTUTcEhF3SDqQtBewqsq8JC2Q1Cmps7u7u+JqmJlZo6oEwFhgXR7f\nAEyqWiNJwNHARuCpKvOKiCUR0R4R7W1tbRVXw8zMGlUlALYAY/L4uD5eU7cmkhOANcDbK87LzMyG\nQZUNcBc9XTXTgbVVaiSdLOnYPG1X4DcV52VmZsNgVIWaZcBKSZOBucB8SYsjYtE2amaSwuUKSccD\n95H6/MfXqTMzsyboNwAiYrOkDmAOcE5ErAdW91OzKT81p9fs+qozM7NhVmUPgIjYSM/ZOwOuaaTO\nzMyGlg/CmpkVygFgZlYoB4CZWaEcAGZmhXIAmJkVygFgZlYoB4CZWaEcAGZmhXIAmJkVygFgZlYo\nB4CZWaEcAGZmhXIAmJkVygFgZlYoB4CZWaEcAGZmhXIAmJkVygFgZlaoSgEgaamkVZIWVa2RtIuk\nGyQtl3S1pB0kjZL0sKQVeZg6WCtiZmaN6TcAJM0DRkbELGBvSVMq1rwHOC8iDgXWA28DpgGXR0RH\nHu4dzJUxM7PqquwBdNDzI+7LgdlVaiLi/Ii4KU9rAx4FZgJHSLor7zE850fpJS2Q1Cmps7u7u/qa\nmJlZQ6oEwFhgXR7fAExqpEbSLGBCRNwB3A0cEhEzgNHAYb1nFBFLIqI9Itrb2toqr4iZmTXmOd/A\n69gCjMnj46gfGnVrJE0EPgO8Mz+3JiKezOOdwHO6k8zMbHhU2QPooqfbZzqwtkqNpB2AK4FTIuKh\n/NwlkqZLGgkcBaweaMPNzGz7VNkDWAaslDQZmAvMl7Q4IhZto2Ym8EFgP+BUSacCFwCnA5cBAr4e\nEd8cvFUxM7NG9BsAEbFZUgcwBzgnItbT65t7nZpNpA3+BXVmOW17G21mZtuvyh4AEbGRnrN8Blxj\nZmatw1cCm5kVygFgZlYoB4CZWaEcAGZmhXIAmJkVygFgZlYoB4CZWaEcAGZmhXIAmJkVygFgZlYo\nB4CZWaEcAGZmhXIAmJkVygFgZlYoB4CZWaEcAGZmhXIAmJkVygFgZlaoSgEgaamkVZIWVa2RtIuk\nGyQtl3S1pB2qzsvMzIZevwEgaR4wMiJmAXtLmlKx5j3AeRFxKLAeeFuVeZmZ2fCosgfQQc+PvS8H\nZlepiYjzI+KmPK0NeLTivMzMbBhUCYCxwLo8vgGY1EiNpFnAhIi4o8q8JC2Q1Cmps7u7u9JKmJlZ\n46oEwBZgTB4f18dr6tZImgh8Bjiu6rwiYklEtEdEe1tbW5V1MDOzAagSAF30dNVMB9ZWqckHfa8E\nTomIhxqYl5mZDYNRFWqWASslTQbmAvMlLY6IRduomQl8ENgPOFXSqcAFfdSZmVkT9BsAEbFZUgcw\nBzgnItYDq/up2UTa4F/Qe3516szMrAmq7AEQERvpOXtnwDWN1JmZ2dDylcBmZoVyAJiZFcoBYGZW\nKAeAmVmhHABmZoVyAJiZFarSaaBm1jr2XHh905a99qzDm7ZsG3zeAzAzK5QDwMysUA4AM7NCOQDM\nzArlADAzK5QDwMysUA4AM7NCOQDMzArlADAzK5QDwMysUA4AM7NCOQDMzApVKQAkLZW0StKiRmok\nTZK0subxSyU9ImlFHtq2r/lmZjZQ/QaApHnAyIiYBewtaUqVGkkTgIuBsTWl+wNnRERHHroHZzXM\nzKxRVfYAOoAr8vhyYHbFmmeAo4HNNXUzgeMlfVfSmfUWJmmBpE5Jnd3dzgczs6FSJQDGAuvy+AZg\nUpWaiNgcEZt61d1ACos3ArMkTes9o4hYEhHtEdHe1uYeIjOzoVIlALYAY/L4uD5eU6UG4PaIeCwi\nngHuAZ7TnWRmZsOjSgB00dPtMx1YO8AagBslvUTSzsChwH2VW2pmZoOqyk9CLgNWSpoMzAXmS1oc\nEYu2UTOzj3mdBtwM/B74fEQ8OPCmm5nZ9ug3ACJis6QOYA5wTkSsB1b3U7Op5rmOmvGbgX0GpeVm\nZrZdKv0ofERspOcsnwHXmJlZ6/CVwGZmhXIAmJkVygFgZlYoB4CZWaEcAGZmhXIAmJkVygFgZlYo\nB4CZWaEcAGZmhXIAmJkVygFgZlYoB4CZWaEcAGZmhXIAmJkVygFgZlYoB4CZWaEq/SCMPT/sufD6\nZjfBzJ5HvAdgZlaoSnsAkpYC+wLXR8TiqjWSJgFXRcQB+fFo4GvARGBpRHxx+1eh9fibuJk9H/S7\nByBpHjAyImYBe0uaUqVG0gTgYmBsTelJQFdEvBl4l6Txg7IWZmbWsCpdQB30/Nj7cmB2xZpngKOB\nzX3U3Qq0956RpAWSOiV1dnd3V2iemZkNRJUAGAusy+MbgElVaiJic0RsanReEbEkItojor2tra1C\n88zMbCCqHAPYAozJ4+OoHxpVamrrNuW6LZVbatZifKzHnu+q7AF00dPtMx1YO8CaRurMzGyIVdkD\nWAaslDQZmAvMl7Q4IhZto2ZmH/O6GPiGpANIZwzdOfCmm5nZ9uh3DyAiNpMO3t4BHBQRq3tt/OvV\nbKp5rqNm/CFgDnAbcEhEPLP9q2BmZgNR6TqAiNhIz9k7A67JdT+vUmdmZkPLVwKbmRXKAWBmVigH\ngJlZoRwAZmaFcgCYmRXKAWBmVigHgJlZoRwAZmaFcgCYmRXKAWBmVigHgJlZoRwAZmaFcgCYmRXK\nAWBmVigHgJlZoRwAZmaFcgCYmRXKAWBmVqhKASBpqaRVkhY1UtN7mqRRkh6WtCIPU7d/FczMbCD6\nDQBJ84CRETEL2FvSlCo1fbxuGnB5RHTk4d7BXR0zM6uqyh5ABz0/4r4cmF2xpt60mcARku7KewfP\n+VF6SQskdUrq7O7urrgaZmbWqCoBMBZYl8c3AJMq1tSbdjdwSETMAEYDh/WeUUQsiYj2iGhva2ur\nuh5mZtag53wDr2MLMCaPj6N+aNSrqTdtTUQ8mad1As/pTjIzs+FRZQ+gi55un+nA2oo19aZdImm6\npJHAUcDqgTTazMy2X5U9gGXASkmTgbnAfEmLI2LRNmpmAlFn2hrgMkDA1yPim4O3KmZm1oh+AyAi\nNkvqAOYA50TEenp9c69TswmgzrRNpDOBzMysyarsARARG+k5o6dyTZXXmZlZc/hKYDOzQlXaAzAz\nA9hz4fVNWe7asw5vynJf6LwHYGZWKAeAmVmhHABmZoVyAJiZFcoBYGZWKAeAmVmhHABmZoVyAJiZ\nFcoBYGZWKAeAmVmhHABmZoVyAJiZFcoBYGZWKAeAmVmhfDtoM2t5vg310HhBB0Cz/tOYmT0fVOoC\nkrRU0ipJixqpqTrNzMyGX797AJLmASMjYpakL0qaEhE/7K8GmFplWu95mZm1imb2IgxH91OVLqAO\nen7YfTkwG+i90a5X8/qK03qHyQJgQX64RdKDFdo4GHYDfjVMy2qU2zYwbtvAuG0DM6ht09nb9fI9\nqhRVCYCxwLo8vgHYr2JN1WnPEhFLgCUV2jWoJHVGRPtwL7cKt21g3LaBcdsGppXb1pcqxwC2AGPy\n+Lg+XlOvpuo0MzNrgiob4C5SVw3AdGBtxZqq08zMrAmqdAEtA1ZKmgzMBeZLWhwRi7ZRMxOIitNa\nxbB3OzXAbRsYt21g3LaBaeW21aWI6L9ImgDMAW6NiPVVa6pOMzOz4VcpAMzM7IXHB2GtYZImSpoj\nabdmt8XMBq7oAJA0SdLKPD5a0rWSbpN0XJPbtYukGyQtl3S1pB1a5Qrq3IV3HTADuFlSW6u0Df74\nmd6Tx1uiXZJGSXpY0oo8TJV0mqS7JX2umW2rJel8SUfm8VZ57z5S8759T9KFLdS2CZK+IalT0oV5\nWku0rapiAyBvyC4mXZsAcBLQFRFvBt4laXzTGgfvAc6LiEOB9cB88hXUwN75qupmmQZ8LCLOAG4E\nDm6htgGcC4ypvTq9Bdo1Dbg8IjoiogPYgXQ23AzgUUmHNLFtAEg6ANg9Iq5tpfcuIi6oed9WAj9u\nlbYB7wO+ks/9Hy/pn1qobZUUGwDAM8DRwOb8uIOeq5RvBZp2QUdEnB8RN+WHbcB7ee4V1E0REbdE\nxB2SDiRtwN7aKm2TdDDwW1JodtAi7SKd7XaEpLskLQXeAvxXpANwNwIHNLFtSBoNfAFYK+kdtNZ7\nB4CklwKTgJfROm37NfBaSbsCLwf2onXaVkmxARARmyNiU82k3lcpTxr+Vj2bpFnABOBntFDbJIkU\nnhtJp/Y2vW2SdgD+GViYJ7XS53k3cEhEzABGky6GbJW2ARwL3A+cQwr1E2it9kFq0wW01uf6HdIt\nFz4KPEDas2uVtlVSbADU0VJXKUuaCHwGOI4Wa1skJwBrgDfRGm1bCJwfEb/Jj1vpPVsTEb/I4520\nVtsg3aNrST4t+1LSHnDLtE/SCOAgYAWt9d59EvhwRJwOfB84htZpWyUt38Bh1DJXKedvs1cCp0TE\nQ7RW206WdGx+uCtwFq3RtkOAEyStAF4HHElrtAvgEknTJY0EjiJ9i22VtgH8CNg7j7cDe9Ja7TsA\nuDN3mbXM3wJp73xq/lz3p3X+FqqLiKIHYEX+dw/gf4BPk3bZRzaxTR8hda+syMP7gdXAeaRdzV2a\n2LYJwE2kb4nnA7u0SttqP1PgRa3SLuC1pL2le4EzSF+8bsv/1x4E9mry+zWe9IXjVmBV/ltoifcu\nt+9MYF4eb6XPdUbeZmzJfxMt07aqgy8Eq5FvUTEbuDGefXyg6Vr5CupWbVurtgtA0hjgcOC7EfGT\nZrentxZ/79y2QeIAMDMrlI8BmJkVygFgZlYoB4AVTVm96Q3OZ3dJbx68lpkNPQeAFUXS2fm+TyMl\n/Tvp9L1/r1N6hqTDJI2VtEzSeEmH1sxnnKT/W1N/LPCGPpZ5uqSDJJ0haWGe14359EGzpqnygzBm\nLySjgHcBjwLvJl3I1iZpKnBbRJya6w4GFkfE7yTtCTwFnCPpgYj4WURskfRyScdHxEWki4CeyPfR\nAdgYEX8uaRzpdiOzgBcDu5NOs/xtRDyTL3IiIv4wDOtu9iwOACvNJyLiSUkLgTfSc9HT2aRL+ZE0\nB/h5RPwuv+bpiHhC0mHAK0m35oB0C4ALJT1MulHZJ4HfAa+i55YUuwB/ApwIfA+4PY+/StKtufYo\n4K4hW2OzPjgArBiSPggcL+lTwBHAocBEYEfSlcQ7SjqRdLHWTyTtTwqJl0u6irRxX03a2BMRvwXe\nK+ls4DRgAelGdL8GvpIX+wwpZD4FvJq0BzANOJV0Be6HIsIbf2sKB4AVIyKWSnoSGBcRswEkXQxs\njoiT8uO/AW4gbaxfSrpS927g5Ij4ce95SroIODHvIbyY1PVzbU3JKFI4vI90hehTpCtb3wD8Hmi5\ni8CsHD4IbMXK3/BfDHRLOjNP/gLpJnxExNci3Zb7OtJtr3u//i257ol81tCbSFeB1tqDdBfL95O6\niK4D3kEKgFnAnYO8WmaVOQCsSLmffympC+Z0Up/8xyPiqTrl/wV8QNKIraeHShpL6io6JdcsBC4D\nviPptK0vjIjbSPeI/xbpTptfycv4Lqnv/+4hWUGzCtwFZMXIZ9wcSera+Sbwzoh4OD99POmHWgCU\nBwAiolvStaSbt/1S0oP5qcuBUXW6kT4r6WrgH/J9fj5P+qGaRcBDkvYC/gx4EtiPdItos2HnALCS\n/DXwU1I3zwnAkZKeIv1Iy07ArpJGke6IuWPtCyPiX/J5/x8ADoyInwNIOgK4ISK+WlN7oqS/JP1M\n4ARSF9BPSL8Mti/wJeDjwC+BqyQdU+/4gtlQ883grBiSRjTjfHtJoyLi6TwuYEREPLP1cfiP0JrE\nAWBmVigfBDYzK5QDwMysUA4AM7NCOQDMzArlADAzK9T/AofUHU3mRfCgAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x1ff7eb6f5f8>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.hist(x1,normed=True)\n",
    "plt.xlabel(\"迭代次数\")\n",
    "plt.title(\"平均运行次数为\"+str(sum(x)/2000))\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem 17\n",
    "Pocket PLA的问题，最多更新50次，打乱数据，运行2000遍，计算错误率"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import random\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "plt.rcParams['font.sans-serif']=['SimHei'] #用来正常显示中文标签\n",
    "plt.rcParams['axes.unicode_minus']=False #用来正常显示负号\n",
    "\n",
    "#数据读取\n",
    "filetrain=open('hw1_18_train.txt')\n",
    "filetest=open('hw1_18_test.txt')\n",
    "\n",
    "trian=[]\n",
    "\n",
    "#数据处理\n",
    "def processdata(file):\n",
    "    data=[]\n",
    "    for i in file.readlines():\n",
    "        #增加w0\n",
    "        temp1='1 '+i.replace('\\t',' ').replace('\\n','')\n",
    "        #分隔数据\n",
    "        temp2=temp1.split(' ')\n",
    "        #转化为float\n",
    "        temp3=np.array(list(map(float,temp2)))\n",
    "        #转化为np.array存入数据\n",
    "        data.append(temp3)\n",
    "    return data\n",
    "    \n",
    "train=processdata(filetrain)\n",
    "test=processdata(filetest)\n",
    "\n",
    "#维度\n",
    "n=len(train[0])-1\n",
    "#训练数据组数\n",
    "m=len(train)\n",
    "#测试数据组数\n",
    "m1=len(test)\n",
    "\n",
    "#定义sign函数\n",
    "def sign(x):\n",
    "    if x>0:\n",
    "        return 1\n",
    "    else:\n",
    "        return -1\n",
    "\n",
    "#定义计算错误个数的函数,n为数据维度\n",
    "def CountError(x,w,n):\n",
    "    count=0\n",
    "    for i in x:\n",
    "        if sign(i[:n].dot(w))*i[-1]<0:\n",
    "            count+=1\n",
    "    return count\n",
    "\n",
    "\n",
    "#定义PocketPLA,n为数据维度,m为数据数量,k为步长,max为最大更新次数\n",
    "def PocketPLA(x,k,n,m,maxnum):\n",
    "    #初始化向量\n",
    "    w=np.zeros(n)\n",
    "    #错误率最小的向量\n",
    "    w0=np.zeros(n)\n",
    "    #记录次数\n",
    "    t=0\n",
    "    error=CountError(x,w,n)\n",
    "    if error==0:\n",
    "        pass\n",
    "    else:\n",
    "        #记录取哪个元素\n",
    "        j=0\n",
    "        while (t<maxnum or error==0):\n",
    "            i=x[j]\n",
    "            #print(error)\n",
    "            if sign(i[:n].dot(w))*i[-1]<0:\n",
    "                w+=k*i[-1]*i[:n]\n",
    "                t+=1\n",
    "            error1=CountError(x,w,n)\n",
    "            if error>error1:\n",
    "                w0=w[:]\n",
    "                error=error1\n",
    "            j+=1\n",
    "            if(j>=m):\n",
    "                j=j%m\n",
    "    return w0,error"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "x=[]\n",
    "\n",
    "for i in range(2000):\n",
    "    random.shuffle(train)\n",
    "    error=PocketPLA(train,1,n,m,50)[1]\n",
    "    x.append(error/m1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXEAAAETCAYAAADAuzb1AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAAFtlJREFUeJzt3Xu8XWV95/HPD5JgCJFySaOiNYCM\nqOWiRApKa3TEjuKtlTEgqBSYKDMwdSwtYbBWeKFiK8wLcUQZqEGnVcGKSrkzEm5F4KTFAUqttyAE\nYkPBgNbBir/543nSLDbn5Oyzc/Y55wmf9+u1Xlnr2Wvt/dv75HzXc5512ZGZSJLatNV0FyBJGpwh\nLkkNM8QlqWGGuCQ1zBCXpIYZ4luwiJgfETHddUgaHkN8BouIrSNi6008PisituosfykilnZW+Qhw\n0ia2PzIiXtBZ/r2IeHZELIiId/as+8KI2GGwdwIR8ScRceQE1n99RCwe9PWkpwtDfGZ7A7AqIkbq\ndH9EPFDnVwF/B+zVWf//AT/vLL8a+MJoTxwRC4CzePL/gf8I7ADsDBzbs8nLgesj4rkRcWxE3Nep\nayQiHoqI/TrPf0FE3BARKyNiJfAu4M82LEfEjRFxSU9NH42I19TFdwD7MYaIeG9ErK2vvetY6/Vs\nc35EHNXTdk5E/DQifhQR7xhlm1Mj4kN1fquIWF9fd21E3NJZ77cj4oqIuDQi9u+0f6b+zL4XEYfU\ntu0j4qLa/s2IeMmW0D7W56Yhy0ynGTwBbwFm1fnlwOl1flvgZGDrzrorgLfW+RcCvwTW9kzP7Kz7\nILAKOBS4EXi4Lo8A64FvAfM7z/8mYH/gncCJPXWuAPbqLO8GPKvO/zvgBmAbYG5tewmwZ89z/Abw\nI+CVwJeB14/xmewFrAGeAxwIXNbH53ga8DhwVKftcOBa4FnAq4BHgW06j+9Zt/lQZ/mqUZ57N+Af\nKDud3wXuBwI4BPhcXWdvYB0wC/g45a+kqD/fb9d1mm4f63NzGnJGTHcBTuP8gOBLwCfrfDfETwW+\nWudfCnyHErxrgIvrL9pJPc/1EPAMYClwK7Aj8Exgdn38r+sv4AuAlZ3tfpXSE9+nLr8ZuAW4qTPd\nSieUKUF/Rw24y4GDgBPq+9kDuBs4vLP+bGBr4LXAc4HrgZeO8Zn8MfDRzvKtwLxNfIYvBj4JfI4n\nh/hBwPM6y+uBhXU+ag1fZGOIHw58bJTnPxA4uOdzng/8IXBcp30dsD1wH7BLp/0xyl8/TbeP9bk5\nDXeahWa6Y4C/j4hrNjRExAG1fcNww7eAFwHnA1+j9KZvBk6IiD/JzFPrerMoPaSrKL+M3wXuBM6J\niBMp4bkCSGBRRNwEXAisBt4H7FPXuQr468z8ZaemAOZsWM7Mz0fEPwK/Sekxn0kJsaWUHcWyzLy5\n8z7fTwn+X9TlvYHPdo7LzqYExcJaw8rOtg8Azwf+fozP8J7MPD4iVnQbM/OmTv37Aw9n5o9q07HA\nvcA3gEW17aXA0oh4NyWo/1Nm3pKZt9TnmA28F1iVmY9FxF3AyRHxReBg4AeZub6+p52BNRGxqL63\nx+prtN4+2uemYZruvYjT+BPwCkqveTlwOiW8l4yy3grgrZTe9sspoXozdZgDeKRn/ZuARX3WMAtY\nXef/kjI88k3KL+/KunxNZ/35lDH3A4CjgM9Qwvw2ynDJjXSGX3peay/gzp62fSnhCGVndUjnsf8N\nvKKP97CCTk+857FvAO+t8wspwyM71to/VNv/AHhdnT8UuKvnOc6iHJN4Y13ehrKTvAX4IfCm2n4G\n5S+Rkyg7nou2kPZRPzenIefDdBfgNMYPBl5Tf0FGOtP9lF7nhuW/Bf4R+Pd1mxXUMfHO8+wEnAvs\nDjxU255D6a2vr/+eCxxfn3NlnW4H/rDzPLMoPfIA5tS2vYEbO+vMYeOwyB3AMkrv+k7KkMfVlOGU\nj1PC/ewx3vuZwAcpobhhjP+NwCV1/s+AIzrr/xVwQB+f6QpGCXHgOMoObau6/EXg7XV+zDAC/gn4\n1Z62vWr7fMqQ18m1fW79ee1COZj8buBTlL96Ftd1Wm/v63NzmuSsmO4CnCbww+qMiY/x+ArgQ8Ax\ndflASjC/v4brgz3r/1tPHPgj4NjOY4cBp3aWN4T48yiBfBNlbDQpPfKbKcH/nrruDj2vdTplRzGb\nejC2zs/qWW8fSq/1mZS/OO4BPkEZpji7rrOUjccJAvgBnbHtcT6fo3ra9qUc4N210/YYGw8Erwd+\nApxNGT7ZsM4zKEM/O9fn2L3z2B2UA7dXAW/ptF9M52At5RjBV0eps8n2sT636f692dKnaS/AaQI/\nrDFCvIb11yg99Qspvfh3UMa896vrzAW+37PdTXXdEygH4b7DxgOV/0CnJ1WD+UHgL2qAzQXuqq97\nSs/zvoUyhLCyM91bn7/bdiNwWGe7RZS/LN7caZtLOTj6YeoZMZSAX0M5E+SDwEifn98KnnxgcyfK\njuh3NrHNUWwcTrkWOALYDvgocHNtfxdwXf1cXlJDbA7waeCrlAOrbwIeoe4s6uPfA3695/Wabh/t\nc3Ma7uSBzbZsxejn9m84I+Xtmfk4QERsC1yemT+OiN0p4fJwz3bbUXqYy4AllDMvzq/bH0Y5ALnB\nrpRT8W6g9KD/AriSEqLX14N1H8/MxzPza5Rw/zcRcTqwNjM/Odobq+dQnwuclplf7zz0K5Qe76sp\nwzBk5qMRcShlWOVxSrASEa+g7FAOGe01RnEkZWjp3Ig4t7a9OTNvG2P9/0IZMvgUZQd0eG3/POUY\nxL2Ug7eHZebPI+I0yo7jNsrpiydn5g/qNsdShqLu6nmN1ts1xaLuNdWAiDiVcirdiRPc7jZK8H40\nMy+qbfMoByiPy8wHIuKDlPHrDWdn7Ax8JTP/e11/IfA7lD+T/5RycPG0zMz6XGdSDqouzczrR6nh\nY5QQ/x+jPDaPEvpnZuYVPY99gRLg1wFHZ+bPJvLepS2dIa4JiYidKRfErBnlsV2AB9L/VNKUMcQl\nqWHjjolHxPaUccCtgZ9Szgz4LvD9usoJmXnn0CqUJI1p3J54RPxn4DuZeU09+PMgZVx2zLvjSZKm\nxoSGUyLiy5QLFo6g9MrvBN6Tmb/oWW8Z5YwH5s2bt9+ee+7Z+1SSpE1YtWrVQ5m5YLz1+g7xiDiQ\ncsHGcuD+zHwwIj4HfLnnlLAnWbx4cY6MjPRZtiQJICJWZea499Tv6zzxiNgROAd4G+U0scfrQyOU\nO9JJkqbBuF8KERFzKBeSnJyZ9wKfj4h9onzjzFspd9CTJE2Dfr7Z5xjgZcApUb6h5W7KFWp3ALdk\n5rXDK0+StCnjDqdk5rmUy6G7Th1tXUnS1PI7NiWpYYa4JDXMEJekhhniktSwGX8/8UXLLxt429Vn\n9HtbaUlqkz1xSWqYIS5JDTPEJalhhrgkNcwQl6SGGeKS1DBDXJIaZohLUsMMcUlqmCEuSQ0zxCWp\nYYa4JDXMEJekhhniktQwQ1ySGmaIS1LDDHFJapghLkkNM8QlqWGGuCQ1zBCXpIYZ4pLUMENckhpm\niEtSwwxxSWqYIS5JDTPEJalhhrgkNWzWdBewJVq0/LKBt119xiGTWImkLZ09cUlqmCEuSQ0bN8Qj\nYvuIuCIiro6ISyJiTkRcEBG3RMQHpqJISdLo+umJHwGclZmvA9YChwFbZ+aBwG4RsccwC5QkjW3c\nEM/MT2XmNXVxAXAkcFFdvho4qHebiFgWESMRMbJu3bpJK1aS9GR9j4lHxIHADsB9wJra/DCwsHfd\nzDwvMxdn5uIFCxZMSqGSpKfq6xTDiNgROAd4G/B+YG59aDtm8MFRT/WTtKXr58DmHOBi4OTMvBdY\nxcYhlH2A1UOrTpK0Sf30oo8BXgacEhErgQDeGRFnAW8HBu/uSpI2y7jDKZl5LnButy0ivg4cDPxp\nZq4fUm2SpHEMdNl9Zj7CxjNUJEnTZMYelJQkjc8Ql6SGGeKS1DBDXJIaZohLUsMMcUlqmCEuSQ0z\nxCWpYYa4JDXMEJekhhniktSwge6douHZnHugg/dBl55u7IlLUsMMcUlqmCEuSQ0zxCWpYYa4JDXM\nEJekhnmK4Rg291Q/SZoK9sQlqWGGuCQ1zBCXpIYZ4pLUMENckhpmiEtSwwxxSWqYIS5JDTPEJalh\nhrgkNcwQl6SGGeKS1DBDXJIaZohLUsMMcUlqWF8hHhELI+LGOr9LRNwfESvrtGC4JUqSxjLul0JE\nxA7AhcC82vQbwIcz89xhFiZJGl8/PfEngKXAo3X5AODYiPjbiPjIaBtExLKIGImIkXXr1k1SqZKk\nXuOGeGY+mpnrO01XAEuAlwMHRsTeo2xzXmYuzszFCxY42iJJwzLIgc2/yczHMvMJ4O+APSa5JklS\nnwYJ8asi4tkRsS3wOuCuSa5JktSnQb7t/lTgOuDnwKcz89uTW5IkqV99h3hmLqn/XgfsOayCJEn9\n82IfSWqYIS5JDTPEJalhhrgkNcwQl6SGGeKS1DBDXJIaZohLUsMMcUlqmCEuSQ0zxCWpYYa4JDXM\nEJekhg1yK1ptoRYtv2zgbVefccgkViKpX/bEJalhhrgkNcwQl6SGGeKS1DBDXJIa5tkpW5jNOcNE\nUnvsiUtSwwxxSWqYIS5JDTPEJalhhrgkNcwQl6SGGeKS1DBDXJIaZohLUsMMcUlqmCEuSQ0zxCWp\nYYa4JDXMEJekhhniktSwvkI8IhZGxI11fnZEXBoRN0fE0cMtT5K0KeOGeETsAFwIzKtNJwCrMvOV\nwKERMX+I9UmSNqGfnvgTwFLg0bq8BLiozt8ALJ78siRJ/Rg3xDPz0cxc32maB6yp8w8DC3u3iYhl\nETESESPr1q2bnEolSU8xyIHNnwBz6/x2oz1HZp6XmYszc/GCBQs2pz5J0iYMEuKrgIPq/D7A6kmr\nRpI0IYN82/2FwOUR8ZvAi4FbJ7ckSVK/+u6JZ+aS+u+9wMHAzcBrM/OJ4ZQmSRrPID1xMvMBNp6h\nIkmaJl6xKUkNM8QlqWGGuCQ1zBCXpIYZ4pLUMENckhpmiEtSwwxxSWqYIS5JDTPEJalhhrgkNcwQ\nl6SGGeKS1LCB7mIo9Vq0/LKBt119xiGTWIn09GJPXJIaZohLUsMMcUlqmCEuSQ0zxCWpYYa4JDXM\nEJekhhniktQwQ1ySGmaIS1LDDHFJapghLkkNM8QlqWGGuCQ1zBCXpIYZ4pLUML8UQtNuc75QAvxS\nCT292ROXpIYZ4pLUMENckho24RCPiFkR8cOIWFmnvYZRmCRpfIMc2Nwb+EJmnjTZxUiSJmaQ4ZQD\ngDdGxG0RcUFEeIaLJE2TQUL8duC1mbk/MBt4Q+8KEbEsIkYiYmTdunWbW6MkaQyDhPj/zcwH6/wI\nsEfvCpl5XmYuzszFCxYs2KwCJUljGyTEPx8R+0TE1sBbgW9Nck2SpD4NMp59GvCXQABfz8xrJ7ck\nSVK/JhzimXkX5QwVSdI082IfSWqYIS5JDTPEJalhhrgkNcyrLdW8zbkfufciV+vsiUtSwwxxSWqY\nIS5JDTPEJalhhrgkNcyzU/S05pktap09cUlqmCEuSQ0zxCWpYYa4JDXMEJekhhniktQwQ1ySGmaI\nS1LDDHFJapghLkkNM8QlqWGGuCQ1zBtgSQPy5lmaCQxxaRq4A9BkcThFkhpmiEtSwwxxSWqYIS5J\nDTPEJalhhrgkNcxTDKXGbM7piZvL0xtnHnviktQwQ1ySGmaIS1LDHBOX1LfpGo93LH5sA4d4RFwA\nvBi4LDNPn7ySJGnybO6OZ6bvQAYaTomI3wW2zswDgd0iYo/JLUuS1I/IzIlvFPEJ4MrMvDwiDgPm\nZuZnO48vA5bVxRcC356MYjdhZ+ChIb/GMFj31LLuqWXdm+f5mblgvJUGHU6ZB6yp8w8DL+s+mJnn\nAecN+NwTFhEjmbl4ql5vslj31LLuqWXdU2PQs1N+Asyt89ttxvNIkjbDoOG7Cjiozu8DrJ6UaiRJ\nEzLocMpXgRsj4jnA64EDJq+kgUzZ0M0ks+6pZd1Ty7qnwEAHNgEiYgfgYOCGzFw7qVVJkvoycIhL\nkqafByQlqWGGuCQ1bMaHeERcEBG3RMQHNrHOwoi4sbM8OyIujYibI+Loqan0KTUNUvevRcTKiPhG\nRJwXETE11T6ppgnX3Wn/9Yi4ZrgVjm0za780IvYdboVj1jTI/5XdIuL/RMQdEfHHU1PpU2raZN0R\nsX1EXBERV0fEJRExp5/thm2Qusd6LzPBjA7xfi7vrwdYL6RcgLTBCcCqzHwlcGhEzJ+SgjfWNGjd\n7wGOy8zXAM8D9pqKejs1DVo3dYdzFjB7Kmodpa7Nqf0I4HuZeceUFPvk1x607uOBD2bmvsBvR8S4\nV/ZNpj5vvXEEcFZmvg5YC/yH6b5lx6B1j9E2I8zoEAeWABfV+avZeG561xPAUuDRMba7AZjqq6+6\nr9933Zl5SmbeUxd3Yuov/V3CYJ83wO8B1w2tsvEtYYDaI2JH4EzgkYh49ZBrHM0SBvvM/xnYOyIW\nAtsAPx5ijaNZwjh1Z+anMnPDX2YLgH/qZ7shG/f1R6t7jPcyI8z0EO+9vH9h7wqZ+Whmrp/odkM2\naN0ARMRS4O7MfGB4JY5qoLojYifgSODjQ69wbIN+5v8NuBj4DPCuiHjzUKt8qkHrvpJyfcZ/Bb4B\n/GKYRY6i79+xiDgQ2CEzvzmR7YZk0LrHbJtuMz3EB728f7pvCzDw60fEbsCJwPuGUNd4Bq37DODk\nzPzXoVTVn0FrfynwP+u1DhdRempTadC6lwNHZeYpdfuDh1DbpvRVd/1L5xzg6IlsN0SD1j1q20ww\n00N80Mv7p/u2AAO9fh37/AJw9Fi99CEb9HN7FfCxiFgJ7BsR03F/+UFr/y6wW51fDNw7uWWNa9C6\ndwWeFxHPoNyAbqov+Bi37nrw72LKDv7efrcbsoHqHuO9zAyZOWMn4JnAtygHzO6hfOinj7Huys78\n84G7gbOB2ykHMlqo+2PAg8DKOr2qhbr7aZ+ptQPPAS4HbgauAeY3UvchwPeBxyg7/hn3fxw4Dnik\n8/956Sjbbd9I3U9pm8q6NzXN+Cs2B728v97X5SDgqpyGXm2rtyVotW5ot/anW93T/X6n+/Un24wP\ncUnS2Gb6mLgkaRMMcUlqmCGup42I2H26a5AmmyGuLUJEvCgivtJZ/nJEbBURZ0fEotr8kYh4V0Ts\nGRGrI+LaOq2KiBM6287uzP9+lC8D37A86BepSEPhgU1tESLir4BFwGXAfMppYX8D7Ec5Fe944D7g\n94EvAcdm5vK67RJgz8z8dF2+HfgZ8Evg14AfbngZYFvgtzLzZ1PxvqTx2KtQ8yLiGMpFO+8GfpmZ\n/xIRu2bmoRFxPnA6cF9mPgF8OCJeCBwWERvuqbMDsKLzlFcCtwE7A7tTdgL3AbsAuxvgmknsiat5\nEfEsSg/7MEpgv41yReP3KBd+/Qi4lHKXyLMoV949g3JjqQ3mZL1XTUTMpfTqN9w58LuUnv0bgK/V\nnYE0I9gT15bgX4BbKbfuvZvyRd67dh7/aWbeExH/TPk/vwfwYmB/Si/8SmB2RFxYA3pPSmifBBxD\nuTnW/6LcKfBXgD+fijcl9cMQ15ZgW0poz6cMf+wK/BZwfX38GJ58g6gTKeH9XMo4906UnvlWEXEx\npcd+CnA+sH1d/1+BDwCHR8SczPz5kN+T1BdDXM3LzLURcQnlPhiPU4L51cCL6ird4Y+3UIZc7gau\npYTzYZn5Y4Ao3wS1K3BBXX8BZeewhnIvntmU+7yfP8S3JPXNENeWYhvg9ZQvS7gdOCMzVwBExGV1\nnRdQetxrKWeofIJyF7uvRMQfZeZIZv45neGSiHgfsDYzvzhF70OaEM8T15bi2ZSvz/oDSm95eZTv\nK11JuXMdlDNQjgc+Swn5izLzNsrwyUn1VMNe22BnRzOYZ6dIUsPsiUtSwwxxSWqYIS5JDTPEJalh\nhrgkNez/A4GfBgjn24UeAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x20003881978>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.hist(x,20,normed=True)\n",
    "plt.xlabel(\"错误率\")\n",
    "plt.title(\"平均错误率为\"+str(sum(x)/2000))\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem 19\n",
    "这题只使用普通的的PLA"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 155,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#定义PLA,n为数据维度,m为数据数量,k为步长,max为最大更新次数\n",
    "def PLA(x,k,n,m,maxnum):\n",
    "    #初始化向量\n",
    "    w=np.zeros(n)\n",
    "    #记录次数\n",
    "    t=0\n",
    "    error=CountError(x,w,n)\n",
    "    if error==0:\n",
    "        pass\n",
    "    else:\n",
    "        #记录取哪个元素\n",
    "        j=0\n",
    "        while (t<maxnum or error==0):\n",
    "            i=x[j]\n",
    "            if sign(i[:n].dot(w))*i[-1]<0:\n",
    "                w+=k*i[-1]*i[:n]\n",
    "                t+=1\n",
    "            j+=1\n",
    "            if(j>=m):\n",
    "                j=j%m\n",
    "    return w,CountError(x,w,n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 146,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "x1=[]\n",
    "\n",
    "for i in range(2000):\n",
    "    random.shuffle(train)\n",
    "    error=PLA(train,1,n,m,50)[1]\n",
    "    x1.append(error/m1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 163,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXYAAAETCAYAAAAiZy2MAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAAGLZJREFUeJzt3XucXWV97/HPl5BgSBASMyeKvGJA\nUxELQZgi6UE6cIiVi0jRGhShHvAV9aCH1tomHNILNCigzakVQVNioVSRxHIRELmUhFCbAJPKVctL\na8MlEAiQEIMINPz6x/NMs7vZM3vtyZ49M0++79drvbL22s9a81szk+965lmXrYjAzMzKsdNwF2Bm\nZu3lYDczK4yD3cysMA52M7PCONjNzArjYLeOk7SbJA13HWalcrBbyySNkTRmgPd3lrRTzeurJM2p\nafIFYN4A639M0ttqXv9vSW+S1CXplLq2b5c0aXB7ApL+TNLHWmh/tKTuwX49s05wsNtgHAOskdSb\np8clPZHn1wA/Avavaf8r4OWa10cAVzbasKQuYBH//Xfzd4FJwBTgE3Wr/AZwh6S9JH1C0mM1dfVK\nekbSwTXbXyJppaQVklYApwJf6nst6U5J19TV9EVJR+aXHwUOph+SPiVpff7ae/fXLrcdJ2mppF9J\nWivpqLx8L0k3S3pS0q2S9srLr8vb7ptelnR4fu9kSbdJWiZpRt3X+U1JD0naeaB6rCAR4clTyxPw\nAWDnPD8fWJjndwXOAsbUtL0MOCHPvx14FVhfN72+pu2TwBrgQ8CdwHP5dS/wPHAfsFvN9t8PHAKc\nAny+rs7LgP1rXu8DvDHP/xqwEtgFGJ+XvRPYt24b7waeAv4n8F3g6H6+J/sD64A9gVnAjU2+h2cB\n3wL2IB1gfpqXfxf4VJ4/E7ilwbqTgYeB1+W6eoF3AJ8FVtW0GwPc21/Nnsqchr0AT6NzAq4CLsrz\ntcF+DnBtnn8X8NMcxuuAZcCXgXl123omB9Qc4K4cWq8Hxub3bwD2Bd4GrKhZ73+Qeuwz8+vjgVXA\nP9VMd9UGdQ7/e3PAfx84LIfhVcAM4CHgIzXtx+ZwPArYC7gDeFc/35M/Ab5Y8/ouYMIA38NjgN3z\n/GTgRWAcsIV8YATeAGxpsO65wJk12zk4z08Enq1p93+BHwz374unzk7KP3yzlkiaCPyYFIrvIAXK\nDaTe5sER8VQeZ98JuBS4jtTr/mFeZ2ZEnJO3tYk01LI7cDLwF8ADwFeBz5MC9XEggOnAvwGXA2uB\n38/b2kvSLsArEfFqTZ0CxkXESzXL3k06UPwB8BKwgXRQ2Rd4XUT8sKbtPNLB4D/yogOA+2u+FWOB\nKRExVdI3SAeeK/O61wBnR8SPK3w/Pwx8Gvht4BfAnhHxrKQe4LKImF7Tdhzwk7zfW2qWjwf+HNgj\nIj4paTLw8/y9fAr4RkTc2qwWG/085maDEhFbJJ0E/Csp2AFeAT4WEU/lNq8Cr+YLYAJ4GjiRNJTy\nR5KujogHUtMIYBPwNUkfAX4vItaSDhT9krQc+Fl++bfAXjn43kk6kOxECu/Zuf1upBBfCvwVacjk\nHGA5KejPl/R/cl1ExAXABXnd/YFvR8SBNV//QGBJfjkG2FxT3gukYZYB5QPSOcAfRMTL+YBwnaSb\ngE/x2vMRHyQNz2ypW/53wHGkoRnyui8CF+U6rpY0KyIebFaTjW4OdmtJPol4EfDLmsVvJAXo+3Kb\nnUg9+E9HxD/2NYqIXwH35DbHAwslfRnYmpftCVxPGnL5B0l3k4ZGPk4angCYACyNiC/V1SXg4zkY\nDwC+FhE9+b1xksaSxvbvBC4mDbv8Yd6Py4B/B34H+CPSCdozG+z+x4FlkhYBKyPiWtJfE4/m9zfy\n34N8fP6azZwL3BsRP6j5OqeTDjpdwFfq2p8CnF+/kYj4XUmzge9Keivp3MD5EXFV/j4cChwNONgL\n52C3lkTE7cB+tcskzQcmRsSCAVY9UNIbImKJpFmkYZZvk0LxlbztJ4CDJf0Tqee/VtIfA1+PiEvz\n1zqJbX8h1NqLFGivAG8h9dxXkw4a40jDQUuAIyJiY17nCkkLSSdvvwG8GhFbJa2RtHNE9A2/IGkm\n6eqcXycdFP4+H+R+zLZg7wXeA3wrH2gOIp1b6Jeko/N2D+pblg+AX5O0T973dTXtdwdmkoa0+pa9\nB3g4Ip6OiFvzEMyupL8e+mqDdHXSpoHqsTI42G3I5ACfT7o88B+BlZI+SuqhzomINXlc+MUGq+8j\n6f2kIZx5kj6el08BvlPXdhdSD/a3AJH+KvgX4O6IOK+mng8A8yW9VLPu3qRLMT+U20AaUvla39eR\nNJ104vczEbGZdKnnQcCbSD3rx/K2bgIWSbqddAB4NiL63mv0/Xkbafjk2IjYVPfeG4CPAAfWrfa/\nSFe9bK1ZdgTwKUmnAkcC6yLiBUkrgY9Kuj7Xejyv7f1bgRzs1g59J0nr9V0J8+G+k5eSdgW+HxGb\n8nDBO0mXM9aaSAqguUAPcEFdj33fmrZ7k4aCVpJOZH4L+AHwp6Tr2wG+HBEvRcR1pJO4/6Wvxx4R\nFzXaMUnHApcA50bE92re2oN0QvUI0pU+RMRmSR8CvkQa1z85b+M3SSdRj63b/BmkE8bf07Ybcd8V\nEU+SbuBaHBFP163zW8DqumUXkoaTngAeAU7Ky79JuqTz30kHv3Mj4l8b7aeVxVfF2HaTdA7psr7P\nt7je3aQw/mJELM3LJpCGaD4dEU9I+lPSmPJTebUpwNUR8f9y+6mksfHnSQF3KSnAIm/rL4ETSH8h\n3NGghgtIwf7/G7w3gXQg+MuIuKnuvStJob4cOC0iGv3VYTYsHOxWBElTgF1qx6Nr3nsz8ET4l912\nEA52M7PC+FkxZmaFcbCbmRVmWK6KmTJlSkyfPn04vrSZ2ai1Zs2aZyKiq1m7YQn26dOn09vbOxxf\n2sxs1JL0SJV2HooxMyuMg93MrDAOdjOzwjjYzcwK42A3MyuMg93MrDAOdjOzwjjYzcwKs8M9j336\n/BsHve7a8+sfp21mNvK4x25mVhgHu5lZYRzsZmaFcbCbmRXGwW5mVhgHu5lZYRzsZmaFcbCbmRXG\nwW5mVhgHu5lZYSoFu6TJkmZLmjLUBZmZ2fZpGuySJgE3AIcAyyW95hOyJe0s6VFJK/K0/xDUamZm\nFVR5CNgBwOciYnUO+YOAmxu0uTIi5rW7QDMza03THntE3JFD/XBSr31Vg2aHAsdJulvSEkk73FMj\nzcxGiqpj7ALmABuBVxo0uQc4KiIOAcYCxzTYxlxJvZJ6N2zYsB0lm5nZQCoFeyRnAPcDxzdocn9E\nPJnne4EZDbaxOCK6I6K7q+s1w/RmZtYmVU6ezpN0an65B7CpQbMrJM2UNAY4AbivjTWamVkLqvTY\nFwOnSFoJjAEel7Swrs25wBXAvcCqiLitvWWamVlVTU9yRsRGYHbd4gV1bR4kXRljZmbDzHeempkV\nxsFuZlYYB7uZWWEc7GZmhXGwm5kVxsFuZlYYB7uZWWEc7GZmhXGwm5kVxo/XNaszff6Ng1537fnH\ntrESs8Fxj93MrDAOdjOzwjjYzcwK42A3MyuMg93MrDAOdjOzwjjYzcwK42A3MyuMg93MrDCVgl3S\nZEmzJU0Z6oLMzGz7NA12SZOAG4BDgOWSuvppt0TSKkkLGr1vZmadUaXHfgDwuYg4D7gZOKi+gaQT\ngTERMQvYR9KM9pZpZmZVNQ32iLgjIlZLOpzUa1/VoFkPsDTP3wIcVt9A0lxJvZJ6N2zYsB0lm5nZ\nQCo93VGSgDnARuCVBk0mAOvy/HM06NVHxGJgMUB3d3cMptjh5qf+mdloUOnkaSRnAPcDxzdosgUY\nn+cnVt2umZm1X5WTp/MknZpf7gFsatBsDduGX2YCa9tSnZmZtaxKz3oxcIqklcAY4HFJC+vaXJvb\nLAI+DAx+zMLMzLZL0zH2iNgIzK5bvKCuzWZJPbndhRHxfNsqNDOzlrTto/HyAWBp04ZmZjakfJLT\nzKwwDnYzs8I42M3MCuNgNzMrjIPdzKwwDnYzs8I42M3MCuNgNzMrjIPdzKwwDnYzs8K07ZECZuZn\n9tvI4B67mVlhHOxmZoVxsJuZFcbBbmZWGAe7mVlhRuVVMdtz5YGZWencYzczK0zTHruk3YHvkD7I\n+gVgTkS8XNdmZ+DneQL4bEQ80OZazcysgio99pOBRRHxXmA98L4GbQ4AroyInjw51M3MhknTHntE\nXFzzsgt4ukGzQ4HjJB0BPAB8MiL+oz0lmplZKyqfPJU0C5gUEasbvH0PcFREPCnp74BjgO/VrT8X\nmAswbdq0wVe8A9rek8W+Vd1sx1Lp5KmkycBXgdP6aXJ/RDyZ53uBGfUNImJxRHRHRHdXV9egijUz\ns+aaBrukccAy4KyIeKSfZldImilpDHACcF8bazQzsxZUGYo5HTgIOFvS2cByYGxELKhpcy7wbUDA\n9yLitrZXamZmlVQ5eXoJcEmTNg+SrowxM7Nh5huUzMwK42A3MyuMg93MrDCj8iFgo5EfXGZmneJg\ntwH5MzzNRh8PxZiZFcbBbmZWGAe7mVlhHOxmZoVxsJuZFcZXxdiQ8RU1ZsPDPXYzs8I42M3MCuOh\nmB2A73o127G4x25mVhgHu5lZYRzsZmaFcbCbmRXGwW5mVhgHu5lZYZoGu6TdJd0k6RZJ10ga10+7\nJZJWSVrQ/jLNzKyqKj32k4FFEfFeYD3wvvoGkk4ExkTELGAfSTPaW6aZmVXV9AaliLi45mUX8HSD\nZj3A0jx/C3AY8NPaBpLmAnMBpk2bNohSzcysispj7JJmAZMiYnWDtycA6/L8c8DU+gYRsTgiuiOi\nu6ura1DFmplZc5UeKSBpMvBV4IP9NNkCjM/zE/FJWTOzYdM02PPJ0mXAWRHxSD/N1pCGX1YDM4GH\n21ah2SD4+Ti2I6vSYz8dOAg4W9LZwHJgbETUXv1yLXCnpD2Bo4FD216pmZlVUuXk6SXAJU3abJbU\nA8wGLoyI59tTnpmZtaptj+2NiI1suzLGzMyGiU9ympkVxsFuZlYYf4KSjUi+qsVs8NxjNzMrjIPd\nzKwwDnYzs8I42M3MCuNgNzMrjIPdzKwwDnYzs8I42M3MCuNgNzMrjIPdzKwwDnYzs8I42M3MCuNg\nNzMrjIPdzKwwDnYzs8JUCnZJUyXdOcD7b5b0uKQVeepqX4lmZtaKph+0IWkScDkwYYBm7wbOyx98\nbWZmw6hKj30rMAfYPECbQ4FPSPoXSV9oS2VmZjYoTYM9IjZHxPNNmt0E9AC/AcySdEB9A0lzJfVK\n6t2wYcOgijUzs+badfL0nyPiFxGxFfgRMKO+QUQsjojuiOju6vIQvJnZUGlXsN8s6U2SdgXeCzzY\npu2amVmLmp48rSfpSGC/iLioZvE5wHLgZeDrEfFwm+ozM7MWVQ72iOjJ/94O3F733nJg37ZWZmZm\ng+IblMzMCuNgNzMrjIPdzKwwDnYzs8I42M3MCuNgNzMrjIPdzKwwDnYzs8I42M3MCuNgNzMrjIPd\nzKwwLT8EzMxGnunzb9yu9deef2ybKrGRwD12M7PCuMduZsNme/7S8F8Z/XOP3cysMA52M7PCONjN\nzArjMXYz2y7be0WOtZ+D3WyEcEBau3goxsysMJWCXdJUSXcO8P5YSddL+qGk09pXnpmZtarpUIyk\nScDlwIQBmn0WWBMRfy7p+5KWRcQv2lWkmdlIMtKvv68yxr4VmANcN0CbHmB+nl8JdAPLaxtImgvM\nBZg2bVqrdZrZEPL4flmaDsVExOaIeL5JswnAujz/HDC1wXYWR0R3RHR3dXW1XqmZmVXSrqtitgDj\ngeeBifm1mdmIVPpfKO26KmYNcFienwmsbdN2zcysRS332CUdCewXERfVLL4c+L6k9wD7AXe1qT4z\nM2tR5R57RPTkf2+vC3Ui4hFgNvBD4KiI2NrOIs3MrLq23XkaEU8AS9u1PTMzGxzfeWpmVhgHu5lZ\nYRzsZmaFcbCbmRXGwW5mVhgHu5lZYRzsZmaFcbCbmRXGwW5mVhgHu5lZYRzsZmaFcbCbmRXGwW5m\nVhgHu5lZYRzsZmaFcbCbmRWmbR+0YWbWSaV/IPX2cI/dzKwwDnYzs8JUCnZJSyStkrSgn/d3lvSo\npBV52r+9ZZqZWVVNg13SicCYiJgF7CNpRoNmBwBXRkRPnh5od6FmZlZNlR57D7A0z98CHNagzaHA\ncZLuzr3715yUlTRXUq+k3g0bNgy6YDMzG1iVYJ8ArMvzzwFTG7S5BzgqIg4BxgLH1DeIiMUR0R0R\n3V1dXYOt18zMmqhyueMWYHyen0jjg8H9EfFSnu8FGg3XmJlZB1Tpsa9h2/DLTGBtgzZXSJopaQxw\nAnBfe8ozM7NWVQn2a4FTJC0CPgw8JGlhXZtzgSuAe4FVEXFbe8s0M7Oqmg7FRMRmST3AbODCiFhP\nXY88Ih4kXRljZmbDrNIjBSJiI9uujDEzsxHMd56amRXGwW5mVhgHu5lZYRzsZmaFcbCbmRXGwW5m\nVhgHu5lZYRzsZmaFcbCbmRXGwW5mVhgHu5lZYRzsZmaFcbCbmRXGwW5mVhgHu5lZYRzsZmaFcbCb\nmRXGwW5mVphKwS5piaRVkhZsTxszMxt6TYNd0onAmIiYBewjacZg2piZWWdU+TDrHrZ9kPUtwGHA\nT1ttI2kuMDe/3CLp4dbLbWgK8EybtjXSeV/L5H0tU8N91QXbtc23VGlUJdgnAOvy/HPAQYNpExGL\ngcVVimqFpN6I6G73dkci72uZvK9lGs59rTLGvgUYn+cn9rNOlTZmZtYBVQJ4DWloBWAmsHaQbczM\nrAOqDMVcC9wpaU/gaOAkSQsjYsEAbQ5tf6n9avvwzgjmfS2T97VMw7aviojmjaRJwGxgZUSsH2wb\nMzMbepWC3czMRg+f5DQzK4yD3UY8SZMlzZY0ZbhrMRsNRk2wV3yswVRJd3ayrqHQbF8l7S7pJkm3\nSLpG0rhO19guFfZ1EnADcAiwXFJXRwtso6qP3ci/xz/qVF1DocLPdWdJj0pakaf9O11ju7Twc71Y\n0vs7UdOoCPaKjzWYBFxOullq1Kr4eIaTgUUR8V5gPfC+TtbYLhX39QDgcxFxHnAzjW+QG/FafOzG\nl9l2X8io08LP9cqI6MnTA52tsj2q/lwlvQd4Y0Rc34m6RkWw0/iRBfW2AnOAzR2qaaj00GRfI+Li\niLg1v+wCnu5MaW3XQ/N9vSMiVks6nNRrX9W58tqqh+a/w0g6EniBdMAerXpovq+HAsdJujv3eKtc\nej0S9dBkXyWNBf4GWCvpA50oarQEe/0jC6bWN4iIzRHxfEerGhpN97WPpFnApIhY3YnChkClfZUk\n0kF7I/BKZ0pru6b7mofU/gSY38G6hkKVn+s9wFERcQgwFjimQ7W1W5V9PRX4MXAhcIikzw51UaMl\n2HekRxZU2ldJk4GvAqd1qK6hUGlfIzkDuB84vkO1tVuVfZ0PXBwRmzpW1dCosq/3R8STeb4XGK1P\nhK2yr+8CFuf7e/4eOGKoixotAbkjPbKg6b7mnt0y4KyIeKRzpbVdlX2dJ+nU/HIPYLSGXpXf4aOA\nMyStAA6UdGlnSmu7Kvt6haSZksYAJwD3dai2dquyrz8D9snz3cDQ/5+NiBE/Aa8n/eAXAT/J38CF\n/bRdMdz1DvW+Ap8mDUusyNOc4a57CPd1EnArsBK4mHxT3WibWvkdzu1XDHfNQ/xz/XXSX2APAOcN\nd81DvK+7kTpiK0nniN481HWNmjtPd6RHFnhfy+R9LdNI3NdRE+xmZlbNaBljNzOzihzsZmaFcbDb\nDk3SW4e7BrN2c7BbsSS9Q9LVNa+/K2knSV+RND0v/oKkUyXtK2mtpNvytKb2RpJ892Df/JmSTqp5\nPVrvmrRC+eSpFUvSPwDTgRtJl5zNAf4ZOBj4OfAZ4DHgTOAq4BMRMT+v2wPsGxFfz6/vAV4EXgWm\nAY/2fRlgV+DwiHixE/tl1ox7GlYkSaeTbgz5PeDViPilpL0j4kP5xp+FwGMRsRU4T9LbSR/72Pep\n8pOAy2o2+QPgbmAK8FbSgeEx4M3AWx3qNpK4x25FkvRGUk/8JFKIfxDYG/g34C3AU8D1wCdJN5cs\nA15Hephcn3ER8UTe3nhS77/vCaI/I/0FcAxwXT5AmI0I7rFbqX4J3AXsDzxE+sD1vWvefyEifiLp\nWdL/gxnAfqQnSE4i9dDHSro8h/a+pCCfB5wOfIP0xL5NpEcdfLMTO2VWhYPdSrUrKch3Iw2d7A0c\nDtyR3z+ddLdgn8+TAn0v0rj5G0g9+J0kLSP17M8GLgV2z+1fARYAH5E0LiJeHuJ9MqvEwW5Fioj1\nkq4hPbvjJVJYHwG8IzepHTr5AGm45iHgNlJgnxT5KYuSTiMdGJbk9l2kA8Y64Cukx84+Qwp9s2Hn\nYLeS7QIcDTxLev73+RFxGYCkG3Obt5F65utJV8b8NekJfVdL+uOI6I2Ib1Iz1CLp94H1EfGdDu2H\nWUt8HbuV7E2kjxD8Q1Kven7fZ2ySnsoH6cqXzwB/Swr+pRFxN2noZV6+7LHeLrhTZCOYr4oxMyuM\ne+xmZoVxsJuZFcbBbmZWGAe7mVlhHOxmZoX5T/6jrnJdLTREAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x1ff7e9fc828>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.hist(x1,20,normed=True)\n",
    "plt.xlabel(\"错误率\")\n",
    "plt.title(\"平均错误率为\"+str(sum(x1)/2000))\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem 20"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 164,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import random\n",
    "\n",
    "x2=[]\n",
    "\n",
    "for i in range(2000):\n",
    "    random.shuffle(train)\n",
    "    error=PocketPLA(train,1,n,m,100)[1]\n",
    "    x2.append(error/m1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 166,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXEAAAETCAYAAADAuzb1AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAAGNJJREFUeJzt3XmUXFW5xuHfSwYMECCSNoAISSAK\nyGwUIlwMLFEjC/AiSEBEposTzghBogKXIQwGuTJIIIAjEpBBjAiIhAAydQRBxAGvYQgGwxRGgUu+\n+8febU6Kru5Kpau7d/I+a9XKmeurU13v2bXPqRNFBGZmVqaV+roAMzNrnkPczKxgDnEzs4I5xM3M\nCuYQNzMrmEN8OSRpqCT1dR1m1noO8X5I0gBJA7qYP1DSSpXxSyXtU1nkJOCoLtbfX9JGlfGDJK0j\nqU3SJ2qWfYekYc29EpD0LUn7L8XyEySNbfb5zFY0DvH+6cPAHEnt+fGYpMfz8BzgHmDzyvL/Al6t\njO8EXNLZhiW1AVNZ8r3fGxgGDAcOrVnl3cDNktaTdKikRyt1tUt6UtK7KtufLmm2pFmSZgEHAKd1\njEu6RdKVNTWdLGnnPLof8C7qkPRpSfPzc4+qt1zNOhdIOrBm2vGS/inpRklvrpn3XkkPSBqYx8/K\nz9nxeFnSAZXlR0l6RNIalWnfzO/bY5IO6q7+zurJB/PzJS2QdJmklfP0VSVdlZc/p7KNEZJuzts/\npjJ9Y0n3SJpX3Q+Stpf0F0l/l/ShyvSP5NfzoKRtGqj9g5KulXSNpPfU7MvJko7t5i2yZRERfvTD\nB7AHMDAPTwJOyMOrAEcDAyrLXgx8JA+/A1gEzK95rF5Z9h/AHGAv4Bbg6TzeDiwEfg8MrWx/N+A9\nwCeAI2rqvBjYvDI+Glg7D78dmA2sDAzJ094JbFyzjW2BJ4DtgcuBCXX2yebAPGBdYBwws4H9eDzw\nCnBgZdquwP3A6sC+wDmVeQOAe7uoYRDwYMdrzNOuAT5TGd8MuDFv623AP4ER9eqvVw/wOeAGYHB+\nz4/M008DLiIdiL8HfCxPvww4Lj/vTGDbPP1u4CDgTcCduabBwGPAzsBa+T1fBXgL8GR+nzYE2rva\n9/n9/hPpwLtn3qbyvP8CXgKO7evP0/L86PMC/KjzxsClwFl5uBrixwFX5eGtgb+Sgnde/hCfDhxV\ns60n8wd4n/whfnMOjEF5/i+AjYGNgFmV9d5Caolvmcd3B24Hbq087qQSyqSgvzd/uH8J7AB8Pr+e\nMcADwL6V5Qfl0Hk/sB5wM7B1nX3yDeDkyvidwKpd7MNNgbOAH7BkiE8HPpWHBdxfmfcF4FddbPNg\n4IzK+O7AH1jyoLo3cEpl/G5gy3r116uHdCD4YB5eA7gtD/8NeEce3gL4Sd6PL3Tsj1zXSaTAfrwS\nrF8ADgP+A7i9UstU4AP5/bukMv0K0sG4Xu3jgF1q/taG5nk/A07BId7Sx0CsvzoE+KOkGzomSNou\nT+/obvg9sAlwAXA1qTV9G/B5Sd+KiOPycgNJrdHrSF0mD5Faft+VdAQpPC8GAhgp6Vbg+8Bc4Euk\nAFovr/+LiFhUqUmkVh0AEfFDSX8hhcS6wLeBBaQDyMbAYRFxW+V1foUUHP+Xx7cALqqclx0EDI+I\nEbmGWZV1Hwc2AP5YZx8+GBGHS7q4Zvp6eZ8RESHpNUmrkr4xHA/cL+ly4LyIuKFm3S8A/5lf+yDg\nDOBZ4GeSLomIS3M9x0v6DunAOJzUev9snfrr1bMecF+evjB3hZG395c8/HDlOeZFxIuV6fvnbdwf\nOWHz9O2B5zu2XbOdNepM73TfR8TtlX3xaWBORDyfl/mou1JazyHeT0XEC5Imkr6qbpInvwbsHxFP\n5GUWAYty4AXpa/uepHD/mqQrIuL+tGgEKWzOlrQv8MmImEvqvqhL0k2k0If0FX49SYNJX7fnkL7S\nvwLskpcfSgrsGcB3SC2144CbgC8DUyR9NtdFRJxCaq0haXPgJxGxVeX5tyK1VCG12J+rlPcisGYX\n+7DejYFqt/MSKbwOBF4mtd7XBK6QNC4i/pBrGQf8IyL+ntfbm9RNciLpnMRZkhaSDnaPkro0hgKn\nR8SrSierO6u/Xj210zs+ry9VXlu9bTQz/S2k9/OZpdhOh1OAw0l/f9aLHOL9TD7Bdxbpg9xhbdKH\n60N5mZWA1Uj9sDd2LBQR/yJ9dUfS7sAJkk4HXs/T1iX1325EajneRereOJD0VRzS1+AZEXFaTV0i\ndUm8KmkL4OyIGJ/nDc4tsUWkPvZzSF0nX82v42Lg76QW7NdIJ0+/2MnLPxC4TNJUYHZEXEVqAT6S\n5z/DksExJD/n0qq3nW2BKbk13fHNZwKpuwRyV0NlvW2B8yPiwrz8hqTzB+sAf4+ID+T36rq8r+s9\nb3fTO1rXb8r/LpKkHOSNbqPR6QuXcnkAIuIrki4CbpS0YaU1bi3mEO9nIuI3pL7cf5M0CVgtIiZ3\nsepWktaKiOm5xfhdUl/pI6QWPBHxOPCu3F2yf0TMlXQk8L2IuCA/10QWt/yr1gMul/QauQtA0h2k\nA8RgUnfAdGCniOhoyf1Q0gmkE6vnAYsi4nVJcyQNjIiOLhQkbUlq2W5GOgD8KB/Q/sjiEG8nddP8\nOB9UtiGdC1ha7aRvCLdJWgUYBTxFamk+UlnuX6RvLx0Hzt2A6nvwHOmkcO3y2+W6iYhFku4FxnZR\nf716OqZfnq8G6Tiw30fqUmvP230sIl6U9IqkEfmb2ljSSca/AGMkDYqI1yrT5wAnV2ofSzqJ+ldS\n/3d1+pWkb3pvqD1/U3o+Iv4WEfdLehxYn9Q4sF7gEC9YDutJpA/0jcBsSfuR+nX3iYg5koaQughq\njZa0G+nDeVTl0rPhwE9rll0ZmAK8j3Ti7W7gd8BdEXFipZ49gEmSXqmsO4rU1bBXXgbSV/OzO55H\n0kjSSdnDI+I50uWV25BatIeQuiYArgWmSvoNKeyfioiOeUvjcmCWpPtI3w5+ExGvSZoN7Cfpmvzc\nuwNn5nW2Ap6IiGpozwaOlTQt76P9Sd8+tgH2UbrEchjpipN9Sd1cb6g/9793Vs8lwHmSFpDOTVyV\nn/cnwHfywf3EPA7p5PG5uS/+aOAreTs3AmdKugr4FPCBiJivdOniZFJ//a7AkaQuuTGSDiV9+9sI\nuIv0LaCz2ncCDpI0gXQ1y9qkA4H1lr4+s+pH9w/g68BJnUxfnxQcK1emrQKsmYc3JAVRe81695JO\nbI4jfdgPrcybSOVqAlKrOEgf/qHAz0lXwKxCCvNjqs/fSY0nkMK53vxdSa3fQ2umr5Nf32+BPSvT\nx5GuirmRxVdovJcuLjckdeccWDNtN1JL9moWXxI5gHT53qOkMDu8svyXyVcL1Wzna6SuoqfIV2/k\n/XQZqWviSeC/u6q/Xj15+iH5/foBS172eXR+D89k8aWog0knkv8ATK4suzpwYV6++l6vQzqg3QPs\nVpm+MXA9cAewXTf7XqRvfU/k5x1fs3+OxVentPTRcdmR9WOSjiNdOnbEUq53F+nqjpMjYkaetiqp\n5faZiHhc0jdJfb1P5NWGA1dExNfz8iNIrcOFwKmkbpPjIyLytr4NfITU8r+5kxpOAeZHxBmdzFuV\nFFrfjohra+ZdQvrR0k3AwRHR2bcJsxWeQ9waImk4qcX9hj5oSW8FHg//MZn1Ooe4mVnBfO8UM7OC\nOcTNzArW8ksMhw8fHiNHjmz105iZLVfmzJnzZES0dbdcy0N85MiRtLe3t/ppzMyWK5IebmQ5d6eY\nmRXMIW5mVjCHuJlZwRziZmYFc4ibmRXMIW5mVjCHuJlZwRziZmYFW67/U4iRk2Y2ve7cKbv2YCVm\nZq3hlriZWcEc4mZmBXOIm5kVzCFuZlYwh7iZWcEc4mZmBXOIm5kVzCFuZlYwh7iZWcEc4mZmBXOI\nm5kVzCFuZlYwh7iZWcEc4mZmBXOIm5kVrMsQlzRM0i8ltUs6L0+bLul2SZN7p0QzM6unu5b4J4Af\nR8RYYKikI4EBETEOGC1pTMsrNDOzuroL8aeAzSStCbwNGAXMyPOuB3bobCVJh+XWe/uCBQt6rFgz\nM1tSdyF+K7AB8AXgQWAwMC/PexoY0dlKETEtIsZGxNi2traeqtXMzGp0F+LfAj4dEccDfwL2A4bk\neas1sL6ZmbVQdyE8DNhc0gBgW2AKi7tQtgTmtq40MzPrTnf/2/3JwEWkLpXbgTOAWyStC0wAtmtt\neWZm1pUuQzwi7gLeWZ0maTywC3BqRCxsXWlmZtad7lribxARz7D4ChUzM+tDPjFpZlYwh7iZWcEc\n4mZmBXOIm5kVzCFuZlYwh7iZWcEc4mZmBXOIm5kVzCFuZlYwh7iZWcEc4mZmBXOIm5kVzCFuZlYw\nh7iZWcEc4mZmBXOIm5kVzCFuZlYwh7iZWcEc4mZmBXOIm5kVzCFuZlYwh7iZWcEc4mZmBXOIm5kV\nzCFuZlYwh7iZWcEc4mZmBXOIm5kVzCFuZlYwh7iZWcEc4mZmBXOIm5kVzCFuZlYwh7iZWcEc4mZm\nBXOIm5kVzCFuZlYwh7iZWcEGNrqgpHOAayPiGknTgU2BmRFxQsuqK9TISTObXnfulF17sBIzW941\n1BKX9B/A2jnA9wQGRMQ4YLSkMS2t0MzM6uo2xCUNAs4H5kraAxgPzMizrwd2aFl1ZmbWpUZa4gcA\nfwROBd4DfA6Yl+c9DYyoXUHSYZLaJbUvWLCgp2o1M7MajYT41sC0iJgP/AiYDQzJ81brbBsRMS0i\nxkbE2La2th4r1szMltRIiD8EjM7DY4GRLO5C2RKY2+NVmZlZQxq5OmU6cKGkicAgUp/4zyWtC0wA\ntmtdeWZm1pVuQzwingf2rk6TNB7YBTg1Iha2pjQzM+tOw9eJV0XEMyy+QsXMzPqIf7FpZlYwh7iZ\nWcEc4mZmBXOIm5kVzCFuZlYwh7iZWcEc4mZmBXOIm5kVzCFuZlYwh7iZWcEc4mZmBXOIm5kVzCFu\nZlYwh7iZWcEc4mZmBXOIm5kVzCFuZlYwh7iZWcEc4mZmBXOIm5kVzCFuZlYwh7iZWcEc4mZmBXOI\nm5kVzCFuZlYwh7iZWcEc4mZmBXOIm5kVzCFuZlYwh7iZWcEc4mZmBXOIm5kVzCFuZlYwh7iZWcEc\n4mZmBRvY1wX0VyMnzezrEszMuuWWuJlZwRziZmYFc4ibmRWsoRCXNELSPXl4uqTbJU1ubWlmZtad\nRlvipwNDJO0JDIiIccBoSWNaV5qZmXWn2xCXtDPwIjAfGA/MyLOuB3aos85hktoltS9YsKCHSjUz\ns1pdhrikwcA3gEl50qrAvDz8NDCis/UiYlpEjI2IsW1tbT1Vq5mZ1eiuJT4JOCcins3jLwBD8vBq\nDaxvZmYt1N2Pfd4P7Czpc8BWwPrAo8AdwJbAn1tbnpmZdaXLEI+IHTuGJc0CdgdukbQuMAHYrqXV\nmZlZlxruDomI8RHxHOnk5h3AThGxsFWFmZlZ95b63ikR8QyLr1CxHras92yZO2XXHqrEzErgE5Nm\nZgVziJuZFcwhbmZWMIe4mVnBHOJmZgVziJuZFcwhbmZWMIe4mVnBHOJmZgVziJuZFcwhbmZWMIe4\nmVnBHOJmZgVziJuZFcwhbmZWMIe4mVnBHOJmZgVziJuZFcwhbmZWMIe4mVnBHOJmZgVziJuZFcwh\nbmZWMIe4mVnBHOJmZgVziJuZFcwhbmZWMIe4mVnBHOJmZgVziJuZFcwhbmZWMIe4mVnBHOJmZgVz\niJuZFcwhbmZWMIe4mVnBHOJmZgVziJuZFazbEJe0hqRrJV0v6UpJgyVNl3S7pMm9UaSZmXVuYAPL\nfByYGhE3SDoXmAgMiIhxki6UNCYi/traMq03jJw0s+l1507ZtQcrMbNGddsSj4hzIuKGPNoG7A/M\nyOPXAzvUriPpMEntktoXLFjQY8WamdmSGu4TlzQOGAY8CszLk58GRtQuGxHTImJsRIxta2vrkULN\nzOyNGgpxSW8GvgscDLwADMmzVmt0G2Zm1vMaObE5GLgMODoiHgbmsLgLZUtgbsuqMzOzLjXSij4E\n2AY4RtIsQMAnJE0FPgY0fzbMzMyWSbdXp0TEucC51WmSfg7sApwaEQtbVJuZmXWjkUsM3yAinmHx\nFSpmZtZHfFLSzKxgDnEzs4I5xM3MCuYQNzMrmEPczKxgDnEzs4I1dYmh9V/LcidCMyuPW+JmZgVz\nS9x6hO9FbtY33BI3MyuYQ9zMrGAOcTOzgjnEzcwK5hA3MyuYQ9zMrGAOcTOzgjnEzcwK5hA3MyuY\nQ9zMrGAOcTOzgjnEzcwK5htgWdGW9da7vvmWlc4tcTOzgjnEzcwK5hA3MyuYQ9zMrGAOcTOzgjnE\nzcwK5ksMrc8t62WCffXcvjzR+gO3xM3MCuYQNzMrmEPczKxgDnEzs4L16xObfXnCy8ysBG6Jm5kV\nzCFuZlYwh7iZWcEc4mZmBWv6xKak6cCmwMyIOKHnSjIrQ4kn3v0r0+VPUy1xSXsCAyJiHDBa0pie\nLcvMzBrRbEt8PDAjD18P7AD8tWOmpMOAw/LoC5L+3GyBvWw48GRfF9EE1927Sq0bnVJs7Sti3Rs0\nslCzIb4qMC8PPw1sU50ZEdOAaU1uu89Iao+IsX1dx9Jy3b2r1Lqh3Npdd33Nnth8ARiSh1dbhu2Y\nmdkyaDZ855C6UAC2BOb2SDVmZrZUmu1OuQq4RdK6wARgu54rqU8V1wWUue7eVWrdUG7trrsORURz\nK0rDgF2A2RExv0erMjOzhjQd4mZm1vd8QtLMrGAOcbMeImkdSe+XNLSva7EVxwoV4pKmS7pd0uQu\nlhkh6ZbK+CBJ10i6TdLBvVPpG2pa6rrztE0kXd36CuvW1Mz+Xl/SLEm/kTRNknqn2iVqaqbutwOX\nAtsDN0sa3Aul1tbU1N9Jnr6ZpBtaW2HdmprZ32+V9Fj+W5klqa13ql2ipmXZ39dI2qon6lhhQryR\nWwXkk7XfJ/2YqcPngTkRsT2wV2+3spqtW9KGwGnAGr1Va01Nze7vTwGfiYidgbcBm/dGvZWamq17\nC+CgiDgO+F9gVG/UW6mp2brJB8qpwKDeqLXmuZute1vgxIgYnx8Leqfif9e0LPv748DfIuLenqhl\nhQlxOr9VQK3XgX2A5+qsNxvo7V+NVZ9/aep+HvhoSyvr2niaqDsijomIB/PoWvT+T63H01zdlwMP\nS9oVGAY81Noy32A8zf2dABwE3NSyyro2nubq3g44VNLvJJ3U0go7N54m6pb0ZuDbwDOSduqJQlak\nEK+9VcCI2gUi4rmIWLi067VYU3VHxD8j4pVeqK+eZvc3AJL2AR6IiMdbV2KnlqXu1YCPAQ8DvX3Z\nV1N1S1oL2B84veUVdq7Z/X0tKUjfDYyTtEUri+xEs3V/GbgMOA84QNLuy1rIihTizd4qoK9vMdDX\nz9+spuuWNBo4AvhSC+rqTtN1R8SzEfFJUrfEu1tQW1earXsKcHREvNaSqrrXbN2/jYjnI+J14B6g\nt++k2mzdWwNn59/WzCAdiJZJKYHQE5q9VUBf32Kgr5+/WU3VnfsRLwEOrtdKb7Fm6z5X0o55dE3g\n2Z4vrUvN/p28DzhF0ixgK0m9/X8DNFv3dflqoFWADwB/aEFtXWm27oeA0Xl4LOlb27KJiBXiAawO\n/J50AufBvONPqLPsrMrwBsADwJnA3aSTGf2+7q6m9ee6gVOAfwCz8uN9hdQ9CrgVuAX4Rin7u6//\nVpZhf+8E/Am4Dzi8oLrXBX4J3AbcAAxd1lpWqF9sNnurgHyPmB2A66IPWoel3uLAdfcu1927+kvd\nK1SIm5ktb1akPnEzs+WOQ9zMrGAOcVth5F+xmi1XHOK2XMj3ibmiMn65pJUknSlpZJ58kqQDJG0s\naa6kX+fHHEmfr6w7qDL8RUkTK+PN/kcqZi3hE5u2XJD0M2AkMBMYSvq582+Bd5HuZXI48CjwRdKN\nqg6NiEl53fHAxhHxvTx+N/AysAhYH3ik42mAVYAdI+Ll3nhdZt1xq8KKJ+kQ0o8oPgksioiXJI2K\niL0kXQCcADwa6dd9J0p6BzBRUsd9cIYBF1c2+SvgLmA4sCHpIPAo8FZgQwe49SduiVvxJK1NamFP\nJAX2R0k/vvkb6cdaTwDXkO6QOJV074o3kW5Q1GFw5Pu0SBpCatV33IHuIVLL/sPA1flgYNYvuCVu\ny4OXgDtJt619gPQfeVdvBftiRDwo6SnS3/wYYFPgPaRW+K+AQZK+nwN6Y1JoHwUcQrpZ0fmkn9Kv\nCVzYGy/KrBEOcVserEIK7aGk7o9RwI7AzXn+IaRf1nU4ghTe65H6udcitcxXknQZqcV+DHAB6X7s\nRwCvAZOBfSUNjohXW/yazBriELfiRcR8SVeS7l/xCimYdwI2yYtUuz/2IHW5PAD8mhTOEyPiWQCl\n/71pFDA9L99GOjjMI90/ZxDpHucXtPAlmTXMIW7Li5WBCcBTpBuVTYmIiwEkzczLbERqcc8nXaHy\nP6S7z10h6ciIaI+IC6l0l0j6EjA/In7aS6/DbKn4OnFbXqwDTI2Ir5Jay5M6/v9F0h3nIF2Bcjhw\nESnkZ0TEXaTuk6PypYa1VsaNHevHfHWKmVnB3BI3MyuYQ9zMrGAOcTOzgjnEzcwK5hA3MyvY/wOY\nrToDqLJupwAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x1ff0004f908>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.hist(x2,20,normed=True)\n",
    "plt.xlabel(\"错误率\")\n",
    "plt.title(\"平均错误率为\"+str(sum(x2)/2000))\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Problem 21\n",
    "回顾下结论，$ R^2 = {max}_{1\\le n\\le N} ||xn ||^2$,$\\rho = {min}_{1\\le n\\le N} \\frac {y_n(w^{*T} x_n )} {||x_n||}$，那么运行时间$t\\le \\frac {R^2} {\\rho^2}$，题目的意思是问如果所有的$||x_n||$缩短20倍，那么$t$是否也会缩短20倍？  \n",
    "答案是否,由更新规则知$w$是$x_n$的线性组合($w_0=0时$)，所以如果所有$||x_n||$缩短20倍，那么$||w||$也会缩短20倍，那么$\\rho$缩短20倍，然后$R$缩短20倍，所以$\\frac {R^2} {\\rho^2}$不变，所以时间上界不会改变。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
